Find the Count of Numbers Which Are Not Special - Video Solutions

Problem 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.