Count Primes

Count Primes

What is this problem about?

The "Count Primes interview question" is a classic mathematical challenge. You are given an integer $n$, and you need to find the total number of prime numbers strictly less than $n$. A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself.

Why is this asked in interviews?

Companies like Amazon, Apple, and Microsoft ask the "Count Primes coding problem" to test a candidate's knowledge of number theory and efficient algorithm design. While a brute-force approach (checking primality for every number) is $O(N\sqrt{N})$, interviewers expect the more efficient Sieve of Eratosthenes ($O(N \log \log N)$). It evaluations your ability to trade memory for speed.

Algorithmic pattern used

This problem follows the Sieve of Eratosthenes pattern.

1. Boolean Array: Create a boolean array isPrime of size $n$, initialized to true. Set isPrime[0] and isPrime[1] to false.
2. Sieve Logic: Iterate from $i=2$ up to $\sqrt{n}$.
3. Elimination: If isPrime[i] is true, then all multiples of $i$ (starting from $i imes i$) are composite. Mark them as false in the array.
4. Final Count: After the loop, count how many indices remain true.

Example explanation

$n = 10$

1. Init: [F, F, T, T, T, T, T, T, T, T] (indices 0-9)
2. $i = 2$: Multiples are 4, 6, 8. Mark them false. [F, F, T, T, F, T, F, T, F, T]
3. $i = 3$: Multiple 9. Mark false. [F, F, T, T, F, T, F, T, F, F]
4. End loop (since $\sqrt{10} \approx 3.16$).
5. True indices: {2, 3, 5, 7}. Total count = 4.

Common mistakes candidates make

• Brute Force: Checking every number for primality, which is too slow for large $n$ (like $5 imes 10^6$).
• Off-by-one: Counting $n$ itself when the requirement is "strictly less than $n$".
• Memory Limit: Forgetting that a boolean array of size $10^7$ takes significant memory, though usually acceptable in most environments.

Interview preparation tip

Master the Sieve of Eratosthenes! It is the "gold standard" for prime-related problems. Also, know the time complexity ($O(N \log \log N)$) and be prepared to explain why marking multiples starting from $i imes i$ is an optimization (lower multiples have already been marked by smaller factors).