Watch 10 video solutions for Three Divisors, a easy level problem involving Math, Enumeration, Number Theory. This walkthrough by CodeClips with Abhishek Ranjan has 3,465 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 104Problem Overview: You are given an integer n. The task is to determine whether it has exactly three positive divisors. A number normally has at least two divisors (1 and itself). Only a very specific class of numbers has exactly three.
The key mathematical observation: a number has exactly three divisors if and only if it is the square of a prime number. For example, 4 = 2^2 has divisors 1, 2, 4. Similarly, 9 = 3^2 has 1, 3, 9. This turns the problem into checking whether n is a perfect square and whether its square root is prime.
Approach 1: Optimized Trial Division (O(sqrt(n)) time, O(1) space)
The direct way is to count divisors of n. Iterate from 1 to sqrt(n). For every divisor i, count both i and n / i. Stop early if the count exceeds three. This avoids scanning all numbers up to n and limits work to the square root range. Although the algorithm still checks divisibility repeatedly, it works well for small inputs and clearly demonstrates divisor enumeration using enumeration. Time complexity is O(sqrt(n)) with constant O(1) space.
Approach 2: Prime Square Divisors Check (O(sqrt(n)) time, O(1) space)
This approach uses the mathematical property directly. First compute root = sqrt(n). If root * root != n, the number cannot have exactly three divisors because it is not a perfect square. If it is a perfect square, check whether root is prime by running trial division up to sqrt(root). A prime square guarantees exactly three divisors: 1, the prime itself, and the square. This reduces the divisor counting work significantly and relies on concepts from math and number theory. The overall time complexity remains O(sqrt(n)), but the constant factor is much smaller because only the square root candidate is tested for primality.
Recommended for interviews: Interviewers expect the prime-square observation. Brute divisor counting shows you understand factors, but recognizing that exactly three divisors implies n = p^2 demonstrates stronger mathematical reasoning and pattern recognition. The prime-square check is the cleanest and most efficient solution.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Optimized Trial Division | O(sqrt(n)) | O(1) | Useful when demonstrating divisor enumeration or when mathematical insight is not immediately obvious |
| Prime Square Divisors Check | O(sqrt(n)) | O(1) | Best approach when using number theory insight that numbers with exactly three divisors are squares of primes |