Three Divisors

Difficulty: Easy | Acceptance: 64.20% | Paid: No Topics: Math, Enumeration, Number Theory

Given an integer n, return true if n has exactly three positive divisors. Otherwise, return false.

An integer x is a divisor of n if there is an integer y such that x * y = n.

• Examples
• Constraints
• Approach 1: Brute Force Enumeration
• Approach 2: Square Root Optimization
• Approach 3: Mathematical Property (Square of Prime)

Examples

Example 1:

Input: n = 2
Output: false
Explanation: 2 has only two divisors: 1 and 2.

Example 2:

Input: n = 4
Output: true
Explanation: 4 has three divisors: 1, 2, and 4.

Constraints

1 <= n <= 10^4

Approach 1: Brute Force Enumeration

Intuition The most straightforward way to determine the number of divisors is to iterate through every integer from 1 to n and count how many of them divide n evenly.

Steps

• Initialize a counter to 0.
• Loop through integers i from 1 to n.
• If n is divisible by i (n % i == 0), increment the counter.
• After the loop, return true if the counter is exactly 3, otherwise return false.

class Solution:
    def isThree(self, n: int) -> bool:
        count = 0
        for i in range(1, n + 1):
            if n % i == 0:
                count += 1
        return count == 3

Complexity

• Time: O(n)
• Space: O(1)
• Notes: Simple to implement but inefficient for large values of n.

Approach 2: Square Root Optimization

Intuition Divisors come in pairs. If i divides n, then n/i also divides n. One of these numbers is always less than or equal to the square root of n. We only need to iterate up to the square root of n to find all divisors.

Steps

• Initialize a counter to 0.
• Loop through integers i from 1 while i * i <= n.
• If n is divisible by i:
  • If i * i == n, it means i is the square root of n, so we only add 1 to the counter.
  • Otherwise, we found a pair (i, n/i), so we add 2 to the counter.
• Return true if the counter is exactly 3, otherwise return false.

class Solution:
    def isThree(self, n: int) -> bool:
        count = 0
        i = 1
        while i * i <= n:
            if n % i == 0:
                if i * i == n:
                    count += 1
                else:
                    count += 2
            i += 1
        return count == 3

Complexity

• Time: O(√n)
• Space: O(1)
• Notes: Much faster than brute force, especially as n grows.

Approach 3: Mathematical Property (Square of Prime)

Intuition A number has exactly three divisors if and only if it is the square of a prime number (p²). The divisors of p² are 1, p, and p². We can verify this by checking if n is a perfect square and if its square root is a prime number.

Steps

• Calculate the integer square root of n.
• If the square of the root is not equal to n, return false (n is not a perfect square).
• If the root is less than 2, return false (0 and 1 are not prime).
• Check if the root is a prime number by testing divisibility from 2 up to the square root of the root.
• If the root is prime, return true; otherwise, return false.

class Solution:
    def isThree(self, n: int) -> bool:
        import math
        root = int(math.isqrt(n))
        if root * root != n:
            return False
        if root < 2:
            return False
        for i in range(2, int(math.isqrt(root)) + 1):
            if root % i == 0:
                return False
        return True

Complexity

• Time: O(√n)
• Space: O(1)
• Notes: This is the most mathematically elegant solution and performs similarly to the square root optimization but with a specific logic check.