Count Primes - Solution & Explanation

Problem Overview: Given an integer n, return the number of prime numbers strictly less than n. A prime number is greater than 1 and divisible only by 1 and itself. The challenge is efficiently identifying primes in the range [2, n) without repeatedly performing expensive divisibility checks.

Approach 1: Naive Primality Test (O(n * sqrt(n)) time, O(1) space)

The straightforward method checks each number from 2 to n - 1 and determines whether it is prime. For each number i, iterate from 2 up to sqrt(i) and check if any value divides it evenly. If no divisor exists, the number is prime and the counter increments. The key observation is that factors appear in pairs, so checking beyond sqrt(i) is unnecessary. This approach is easy to implement and useful for understanding the definition of primes, but it becomes slow when n grows large because you repeat divisibility checks for every number.

Approach 2: Sieve of Eratosthenes (O(n log log n) time, O(n) space)

The Sieve of Eratosthenes avoids repeated primality checks by eliminating multiples of known primes. Create a boolean array isPrime of size n initialized to true. Start from 2. If isPrime[i] is true, the number is prime and all multiples of i must be composite. Mark every multiple starting from i * i as false (i * i avoids redundant work because smaller multiples were already handled by previous primes). Continue this process until i * i >= n. Finally, count the indices that remain true. This technique transforms repeated divisibility checks into systematic marking using an array, dramatically improving performance for large ranges.

The algorithm relies on number theory properties: every composite number has a prime factor less than or equal to its square root. Once multiples of smaller primes are removed, remaining numbers must be prime. The approach is a classic example from math and number theory, and it appears frequently in problems involving prime generation, factorization, or divisor counting.

Recommended for interviews: Interviewers expect the Sieve of Eratosthenes. The naive method demonstrates you understand how primality works, but the sieve shows algorithmic optimization and awareness of classic enumeration techniques. For constraints up to millions, the sieve’s O(n log log n) time complexity scales efficiently while keeping the implementation simple.