Three Divisors - Solution & Explanation
Problem Statement
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
Approach Overview
Problem 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 1: Prime Square Divisors Check
The key observation here is that a number n will have exactly three positive divisors if and only if n is a perfect square of a prime number. If n = p^2, then its divisors are 1, p, and p^2, which makes three divisors. To solve this problem, first check if n is a perfect square. If it is, then check if the square root is a prime number.
First, we compute the integer square root of n. If squaring this value doesn't yield n, then n isn't a perfect square, and it cannot have exactly three divisors. Next, we check if this square root is a prime number by attempting to divide it with numbers up to its square root. If it is only divisible by itself and 1, it is prime.
Complexity
Time Complexity: O(sqrt(sqrt(n))) due to the prime checking process.
Space Complexity: O(1) as only a constant amount of space is used.
Approach 2: Optimized Trial Division
Directly counting divisors would involve iterating potentially through all numbers up to n. This can be optimized. We realize that every divisor less than sqrt(n) corresponds to a divisor greater than sqrt(n). Thus, we can iterate only up to sqrt(n) and manage a divisor count effectively.
We iterate through all numbers up to sqrt(n). If i divides n, then n is divisible by both i and n/i, unless i == n/i, in which case it counts as one divisor. We count the divisors and return true if the count equals three.
Complexity
Time Complexity: O(sqrt(n)) due to iterating only up to the square root of n.
Space Complexity: O(1).
Approach 3: Default Approach
Code
Python
Java
C++
Go
JavaScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Prime Square Divisors Check | Time Complexity: O(sqrt(sqrt(n))) due to the prime checking process. |
| Optimized Trial Division | Time Complexity: O(sqrt(n)) due to iterating only up to the square root of |
| Default Approach | — |
Detailed Complexity Analysis
| 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 |
Video Solution
Three Divisors |LeetCode 1952(Easy)| English • CodeClips with Abhishek Ranjan • 3,495 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Three Divisors easy or hard?
How to solve Three Divisors in O(n)?
What is the best approach for Three Divisors?
Is Three Divisors asked at Google/Amazon/Meta?
What data structure is used in Three Divisors?
What is the time complexity of Three Divisors?
Three Divisors Python or Java solution approach?
Ready to solve this problem?
Practice Three Divisors with our built-in code editor and test cases.
Practice on FleetCode