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:
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 <= 109Problem Overview: Given two integers l and r, count how many numbers in this range are not special. A number is special if it has exactly two proper divisors. That property only holds for numbers that are the square of a prime (for example, 4 = 2², 9 = 3²). The task reduces to counting how many prime squares exist in the range and subtracting them from the total numbers.
Approach 1: Brute Force with Optimization (O(n * sqrt(n)) time, O(1) space)
Iterate through every number in the range [l, r]. For each value, count its divisors by checking integers up to sqrt(num). Track how many proper divisors appear. If exactly two proper divisors exist, the number is special. Otherwise it contributes to the answer. This approach directly follows the definition and works for small ranges, but the repeated divisor checks make it slow when r - l is large.
Approach 2: Prime Square Detection (O(sqrt(r)) time, O(1) space)
The key observation from number theory is that only numbers of the form p² where p is prime have exactly two proper divisors. Instead of checking every number, compute integers p such that p² lies inside the range. For each candidate p, run a primality check up to sqrt(p). Every prime found represents one special number. The final answer is (r - l + 1) - countPrimeSquares. This removes the need to examine every number in the interval.
Approach 3: Check for Squares of Primes (O(sqrt(r) * log log r) time, O(sqrt(r)) space)
Instead of repeated primality tests, generate all primes up to sqrt(r) using the Sieve of Eratosthenes. For each prime p, compute p * p and check whether it falls within the interval. This converts many expensive primality checks into a single preprocessing step. The approach relies heavily on mathematical structure and is common in problems involving math and divisor properties.
Approach 4: Mathematical Pattern Recognition for Efficiency (O(sqrt(r)) time, O(sqrt(r)) space)
Recognize that the count of special numbers equals the count of primes p where p² lies in the range. Compute low = ceil(sqrt(l)) and high = floor(sqrt(r)). Then count primes in the interval [low, high] using a sieve or fast prime check. This reframes the task as a prime-counting problem rather than scanning the entire numeric range. It is the cleanest formulation and scales well for large bounds.
Recommended for interviews: Interviewers usually expect the prime-square observation. Start by explaining the brute force divisor check to show you understand the definition, then pivot to the number theory insight that only squares of primes qualify. Implementing a prime check or sieve over sqrt(r) demonstrates strong problem reduction skills and familiarity with array-based sieve techniques.
In this approach, we detect numbers that are perfect squares of prime numbers. These correspond to numbers with exactly 2 proper divisors, which are special numbers. For a number n to be special, it should be p^2 where p is a prime.
By identifying these numbers using a sieve method up to the square root of r, we can count the numbers in the range that are special and compute the non-special count.
This Python solution first computes the sieve of Eratosthenes to find all prime numbers up to the square root of r. It then counts all perfect squares of these primes that lie within the specified range [l, r]. The count is used to determine the number of non-special numbers in the given range.
Python
Time Complexity: O(√r log log √r + n), where n is the number of elements in the range.
Space Complexity: O(√r) for the sieve.
This approach involves checking each number within the range [l, r] to determine if it is special by counting its proper divisors. However, to optimize, we only check up to the square root of the number for its divisors, reducing unnecessary checks.
This Java solution iterates through each number in the range [l, r] and uses an optimized divisor count method which only considers divisors up to the square root of the number. It counts the number of proper divisors and determines whether the number is special based on having exactly 2 proper divisors.
Java
Time Complexity: O(n√d), where n is the range length and d is the average number checked (usually ≤ √r).
Space Complexity: O(1), constant space.
The numbers that have exactly 2 proper divisors are the squares of prime numbers. For example, 4 = 2^2 and 9 = 3^2, both have proper divisors 1 and the prime number itself. Therefore, to solve the problem, you can find all squares of prime numbers in the range [l, r], and count the numbers in this range that are not the square of a prime number.
This implementation checks for all prime numbers up to the square root of r. For each prime, it computes the square and checks if it lies in the range [l, r]. The numbers that are not special are those which are not prime squares within this range.
Python
JavaScript
Time Complexity: O(√r log log r) due to the sieve approach for finding primes, then iterating up to √r for checking primes.
Space Complexity: O(√r) for storing prime numbers and their squares.
Instead of computing which numbers are special, recognize that special numbers up to √r form a limited sequence of squares of all primes ≤ √r. Calculate non-special numbers in the range by identifying these special numbers.
The solution finds squares of all primes ≤ √r and checks if they lie within the range [l, r]. The numbers that do not match these considerable squares are counted as not special.
Time Complexity: O(√r log log r) due to iterating over potential primes up to √r.
Space Complexity: O(1) if we consider the set of prime squares small due to limited elements.
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 cnt in the interval. Finally, we return r - l + 1 - cnt.
The time complexity is O(\sqrt{m}), and the space complexity is O(\sqrt{m}), where m = 10^9.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Prime Square Detection | Time Complexity: O(√r log log √r + n), where n is the number of elements in the range. |
| Brute Force with Optimization | Time Complexity: O(n√d), where |
| Check for Squares of Primes | Time Complexity: O(√r log log r) due to the sieve approach for finding primes, then iterating up to √r for checking primes. |
| Mathematical Pattern Recognition for Efficiency | Time Complexity: O(√r log log r) due to iterating over potential primes up to √r. |
| Mathematics | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force with Divisor Counting | O(n * sqrt(n)) | O(1) | Small ranges or when demonstrating the definition of special numbers |
| Prime Square Detection | O(sqrt(r)) | O(1) | General optimized approach using prime checks |
| Squares of Primes with Sieve | O(sqrt(r) log log r) | O(sqrt(r)) | When many prime checks are required and preprocessing helps |
| Prime Counting via Square Roots | O(sqrt(r)) | O(sqrt(r)) | Best mathematical formulation for large ranges |
Q2. Find the Count of Numbers Which Are Not Special Solution | LEETCODE WEEKLY CONTEST 408 SOLUTION • JUST CODE • 1,089 views views
Watch 9 more video solutions →Practice Find the Count of Numbers Which Are Not Special with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor