You are given 2 positive integers l and r. For any number x, all positive divisors of xexceptx are called the proper divisors of x.
A number is called special if it has exactly 2 proper divisors. For example:
The number 4 is special because it has proper divisors 1 and 2.
The number 6 is not special because it has proper divisors 1, 2, and 3.
Return the count of numbers in the range [l, r] that are notspecial.
Example 1:
Input:l = 5, r = 7
Output:3
Explanation:
There are no special numbers in the range [5, 7].
Example 2:
Input:l = 4, r = 16
Output:11
Explanation:
The special numbers in the range [4, 16] are 4 and 9.
Constraints:
1 <= l <= r <= 109
Solutions
Solution 1: Mathematics
According to the problem description, we can observe that only the squares of prime numbers are special numbers. Therefore, we can first preprocess all prime numbers less than or equal to $\sqrt{10^9}$, and then iterate through the interval $[\lceil\sqrt{l}\rceil, \lfloor\sqrt{r}\rfloor]$, counting the number of primes $\textit{cnt}$ in the interval. Finally, we return $r - l + 1 - \textit{cnt}$.
The time complexity is $O(\sqrt{m})$, and the space complexity is $O(\sqrt{m})$, where $m = 10^9$.