Count Primes - Video Solutions

Problem Overview: You receive an integer n and need to count how many prime numbers exist strictly less than n. A prime number has exactly two divisors: 1 and itself. The challenge is not checking a single number but efficiently counting primes across the entire range [2, n).

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

The straightforward strategy checks every number from 2 to n-1 and determines if it is prime. For each number i, test divisibility from 2 to sqrt(i). If any divisor exists, the number is composite; otherwise it is prime. This works because a factor larger than sqrt(i) would require a smaller complementary factor that would already have been discovered. The algorithm is simple and uses constant extra memory, but it becomes slow as n grows because you repeatedly recompute primality for every number. This approach demonstrates basic math and number theory reasoning, but it does not scale well for large inputs.

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

The Sieve of Eratosthenes precomputes primality for the entire range in one pass. Create a boolean array of size n where each index represents whether the number is prime. Start with all values marked as prime except 0 and 1. Iterate from 2 to sqrt(n). When you encounter a prime number p, mark all multiples of p starting from p * p as non‑prime. Starting at p * p avoids redundant work because smaller multiples were already marked by previous primes. After the sieve finishes, iterate through the array and count the indices still marked as prime. The algorithm relies on sequential marking inside an array, which makes it cache‑friendly and extremely efficient in practice.

The key insight is eliminating repeated work. Instead of checking each number independently, the sieve removes all composite numbers in batches using their smallest prime factor. This dramatically reduces the number of operations and leads to the classic O(n log log n) complexity.

Recommended for interviews: Interviewers typically expect the Sieve of Eratosthenes. The naive primality test shows you understand what defines a prime, but the sieve demonstrates knowledge of classic algorithms and efficient enumeration across ranges. For large inputs (for example n up to millions), the sieve is the only practical solution.