Description
You are given 2 positive integers l and r. For any number x, all positive divisors of x except x 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 not special.
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
Solution
Python3
def generate_primes(n):
isPrime = [True] * (n + 1)
isPrime[0] = isPrime[1] = False
for i in range(2, n + 1):
if isPrime[i]:
for j in range(i * i, n + 1, i):
isPrime[j] = False
return isPrime
primes = generate_primes(int(math.sqrt(10 ** 9)) + 1)
class Solution:
def nonSpecialCount(self, l: int, r: int) -> int:
MAX = int(math.sqrt(r)) + 1
res = 0
for i in range(2, MAX):
if primes[i]:
x = i * i
if l <= x <= r:
res += 1
return (r - l + 1) - res