Three Divisors
EasyPrompt
Given an integer n, return true if n has exactly three positive divisors. Otherwise, return false.
An integer m is a divisor of n if there exists an integer k such that n = k * m.
Example 1:
Input: n = 2
Output: false
Explantion: 2 has only two divisors: 1 and 2.Example 2:
Input: n = 4
Output: true
Explantion: 4 has three divisors: 1, 2, and 4.
Constraints:
1 <= n <= 104
Approaches
3 approaches with complexity analysis and trade-offs.
This approach directly implements the definition of a divisor. We iterate through all numbers from 1 to n and count how many of them divide n evenly. If the final count is exactly 3, we return true; otherwise, we return false.
Algorithm
- If
n < 4, returnfalse. - Initialize a counter
divisorsto 0. - Iterate with a variable
ifrom 1 ton. - In each iteration, check if
nis divisible byi. - If
n % i == 0, incrementdivisors. - After the loop, return
trueifdivisorsis exactly 3, otherwise returnfalse.
Walkthrough
The algorithm starts by initializing a counter for divisors to zero. A small optimization is to note that the smallest number with three divisors is 4, so any n < 4 can be immediately rejected. It then enters a loop that iterates from i = 1 up to the given number n. Inside the loop, it checks if i is a divisor of n using the modulo operator (n % i == 0). If i is a divisor, the counter is incremented. After the loop completes, the algorithm checks if the final count of divisors is equal to 3.
class Solution { public boolean isThree(int n) { if (n < 4) { return false; } int divisors = 0; for (int i = 1; i <= n; i++) { if (n % i == 0) { divisors++; } } return divisors == 3; }}Complexity
Time
`O(n)` - The loop runs `n` times, making the time complexity linear with respect to the input `n`.
Space
`O(1)` - We only use a constant amount of extra space for the counter variable.
Trade-offs
Pros
Very simple to understand and implement directly from the problem definition.
Cons
Inefficient for large values of
ndue to the linear time complexity. It will be too slow ifnis large, though it passes for the given constraints (n <= 10^4).
This approach improves upon the brute-force method by recognizing that divisors come in pairs. If i is a divisor of n, then n/i is also a divisor. We only need to iterate up to the square root of n to find all divisors, which is much more efficient.
Algorithm
- Initialize a counter
countto 0. - Iterate with a variable
ifrom 1 up tofloor(sqrt(n)). - In each iteration, check if
nis divisible byi. - If
n % i == 0:- If
i * i == n, it meansiis the square root, so we incrementcountby 1. - Otherwise,
iandn/iare a pair of distinct divisors, so we incrementcountby 2.
- If
- After the loop, return
trueifcountis exactly 3, otherwise returnfalse.
Walkthrough
The algorithm iterates from i = 1 up to sqrt(n). For each i that divides n, we have found a pair of divisors: i and n/i.
If i * i == n, then i and n/i are the same (i.e., n is a perfect square), so we've found only one unique divisor. We increment our divisor count by one.
If i * i != n, we have found two distinct divisors, i and n/i. We increment our count by two.
After the loop, we check if the total count is 3.
class Solution { public boolean isThree(int n) { // Smallest number with 3 divisors is 4. if (n < 4) { return false; } int count = 0; for (int i = 1; i * i <= n; i++) { if (n % i == 0) { // i is a divisor. // n/i is also a divisor. if (i * i == n) { // If i is the square root, we count it once. count++; } else { // Otherwise, we count both i and n/i. count += 2; } } } return count == 3; }}Complexity
Time
`O(sqrt(n))` - The loop runs up to the square root of `n`, which is a significant improvement over the linear scan.
Space
`O(1)` - We only use a constant amount of extra space.
Trade-offs
Pros
Much faster than the O(n) approach.
Still relatively easy to understand.
Cons
While efficient, it's not the most optimal solution as it doesn't use the core mathematical property of such numbers.
The most efficient approach relies on a key mathematical insight. A number has exactly three positive divisors if and only if it is the square of a prime number. For a prime number p, the divisors of p^2 are 1, p, and p^2. This transforms the problem from counting divisors to checking for this specific property.
Algorithm
- Handle the base case: if
n < 4, returnfalse. - Calculate the integer square root of
n, let's call itroot. - Check if
nis a perfect square by verifying ifroot * root == n. If not, returnfalse. - If
nis a perfect square, check ifrootis a prime number using a helper function. - The
isPrimehelper function checks if a numberpis prime:- Return
falseifp <= 1. - Iterate from 2 up to
sqrt(p). If any number in this range dividesp, returnfalse. - If the loop completes, return
true.
- Return
- Return the result of the primality test on
root.
Walkthrough
The algorithm first checks if n is a perfect square. We can do this by calculating its integer square root, let's call it root, and then checking if root * root equals n. If n is not a perfect square, it cannot have an odd number of divisors, and thus cannot have exactly three. In this case, we return false. If n is a perfect square, we then need to determine if its square root, root, is a prime number. We can use a standard primality test for root. A number p is prime if it's greater than 1 and has no divisors other than 1 and itself. We can check for divisibility from 2 up to sqrt(p). If root is prime, then n has exactly three divisors.
class Solution { public boolean isThree(int n) { // A number n has exactly three divisors if it is a square of a prime number. // Smallest such number is 2*2=4. if (n < 4) { return false; } int root = (int) Math.sqrt(n); // Check if n is a perfect square. if (root * root != n) { return false; } // If it is a perfect square, check if its root is prime. return isPrime(root); } private boolean isPrime(int num) { // 1 is not a prime number. if (num <= 1) { return false; } // Check for factors from 2 up to sqrt(num). for (int i = 2; i * i <= num; i++) { if (num % i == 0) { return false; // Found a factor, so not prime. } } return true; // No factors found, so it's prime. }}Complexity
Time
`O(n^(1/4))` - Calculating `sqrt(n)` is fast. The primality test for `root = sqrt(n)` takes `O(sqrt(root))` time, which is `O(sqrt(sqrt(n)))` or `O(n^(1/4))`. This is the fastest approach.
Space
`O(1)` - No extra space proportional to the input size is used.
Trade-offs
Pros
The most efficient algorithm due to its strong mathematical foundation.
Scales very well for much larger values of
n.
Cons
Requires understanding the number theory behind the problem, making it slightly less intuitive than direct counting methods.
Solutions
Solution
class Solution {public boolean isThree(int n) { int cnt = 0; for (int i = 2; i < n; i++) { if (n % i == 0) { ++cnt; } } return cnt == 1; }}/** * @param {number} n * @return {boolean} */ var isThree = function (n) { let cnt = 0; for (let i = 2; i < n; ++i) { if (n % i == 0) { ++cnt; } } return cnt == 1;};class Solution {public: bool isThree(int n) { int cnt = 0; for (int i = 2; i < n; ++i) { cnt += n % i == 0; } return cnt == 1; }};class Solution: def isThree(self, n: int) -> bool: return sum(n % i == 0 for i in range(2, n)) == 1Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.