1428. Three-Divisor Count
A locker room has lockers numbered 1 to n, and a caretaker marks a locker when its number has exactly three positive divisors. Given n, return how many lockers get marked. A number has exactly three divisors only when it is the square of a prime, because the divisors are then 1, the prime and the square itself. So the task reduces to counting the primes p with p * p <= n. Find the integer square root of n exactly, then use a sieve of Eratosthenes up to it. The expected running time is O(sqrt(n) log log n) with O(sqrt(n)) memory.
Example 1
- Input:
- n = 30
- Output:
- 3
- Explanation:
The numbers 4, 9 and 25 are squares of the primes 2, 3 and 5, so the answer is 3.
Example 2
- Input:
- n = 3
- Output:
- 0
- Explanation:
No prime squared fits in 3, so nothing is marked.
Constraints
1 ≤ n ≤ 1012
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(sqrt(n) log log n)
- Space
- O(sqrt(n))