Count Primes

Count Primes is the standard sieve problem, and the sieve is one of the few algorithms from this section that every interviewer expects you to know by name. The question is simple; the grading is on the two optimisations that make the sieve correct and fast, and on whether you can explain them.

The problem

Given an integer n, return how many prime numbers are strictly less than n. A prime is an integer greater than 1 whose only divisors are 1 and itself.

Example 1. n = 10 → 4. The primes below 10 are 2, 3, 5, 7.

Example 2. n = 30 → 10: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29.

Example 3. n = 0 or n = 1 → 0.

Constraints. 0 ≤ n ≤ 5 × 10⁶.

Clarifying questions

• Strictly less than n? Yes. For n = 7, the answer is 3 (2, 3, 5), not 4.
• Is 1 prime? No. And 0 is not prime.
• How large can n be? 5 × 10⁶ — so a list of n booleans is fine, about 5 MB as a bytearray.

Approach 1: the simple way — trial division

Test each number from 2 to n − 1 on its own. A number k is prime if no d from 2 up to √k divides it. (If k = a × b, one of a and b is at most √k, so checking beyond √k finds nothing new.)

1def is_prime(k: int) -> bool:2    """Trial division up to the square root."""3    if k < 2:4        return False5    d = 26    while d * d <= k:7        if k % d == 0:8            return False9        d += 110    return True111213def count_primes_trial(n: int) -> int:14    return sum(1 for k in range(2, n) if is_prime(k))

Each test costs up to O(√k), so the total is O(n√n). At n = 5 × 10⁶, measured in Python, this took 20.8 seconds. The problem allows about one.

The key insight

Trial division asks every number "are you divisible by anything?" and repeats the same divisions again and again. Flip the question around. Instead of testing each number, take each prime and cross off its multiples. Anything never crossed off is prime.

Start with every number from 2 marked "maybe prime". The first unmarked number, 2, is prime; cross off 4, 6, 8 … The next unmarked number, 3, must be prime (nothing smaller divided it); cross off its multiples. Continue. Each composite number is removed by its prime factors, with no division at all.

Two observations make it fast:

1. Start crossing at p × p. Smaller multiples of p, like 2p or 3p, have a smaller prime factor and were already crossed off by it.
2. Stop the outer loop at √n. Any composite c below n has a prime factor no larger than √c. By the time p passes √n, every composite has been crossed off.

Approach 2: the sieve of Eratosthenes

1def count_primes(n: int) -> int:2    """Count primes below n with the sieve of Eratosthenes."""3    if n < 3:4        return 0                                # no primes below 25    is_prime = [True] * n                       # index k means the number k6    is_prime[0] = is_prime[1] = False7    p = 28    while p * p < n:                            # stop at the square root9        if is_prime[p]:10            for multiple in range(p * p, n, p): # start at p*p11                is_prime[multiple] = False12        p += 113    return sum(is_prime)

Step by step:

1. If n is 0, 1 or 2, there is no prime below n. Return 0.
2. Make a list where index k stands for the number k. Mark 0 and 1 as not prime.
3. For each p with p × p < n: if p is still marked, it is prime; cross off p × p, p × p + p, … up to n − 1.
4. Count what is still marked.

Dry run for n = 30:

What remains is 2, 3, 5, 7, 11, 13, 17, 19, 23, 29: 10 primes. 7 was never used to cross anything off, because its first new multiple, 49, is beyond 30 — the √n stop in action.

Complexity. O(n log log n) time. The inner loop for prime p runs about n/p times, and the sum of n/p over primes p up to n is n × log log n — which is nearly linear, since log log (5 × 10⁶) is about 2.7. O(n) space for the list.

Measured at n = 5 × 10⁶: this version took under half a second, against 20.8 seconds for trial division, and both returned 348,513. Every n from 0 to 299 and 50 random larger values matched trial division exactly.

Approach 3: the same sieve, faster in Python

The Python loop that crosses off multiples is the slow part. Slice assignment on a bytearray does the same crossing-off in C:

1import math234def count_primes_fast(n: int) -> int:5    """Sieve with slice assignment: the crossing-off runs in C."""6    if n < 3:7        return 08    is_prime = bytearray([1]) * n9    is_prime[0] = is_prime[1] = 010    for p in range(2, math.isqrt(n - 1) + 1):11        if is_prime[p]:12            is_prime[p * p::p] = bytes(len(range(p * p, n, p)))  # zeros for every multiple13    return sum(is_prime)

Same algorithm, same O(n log log n), but at n = 5 × 10⁶ it ran in 0.025 seconds. A bytearray also uses one byte per number instead of an 8-byte list slot. Mention this after the plain version; do not lead with it.

Edge cases

• n = 0, 1, 2. No primes below; return 0. The early return also avoids indexing is_prime[1] in a list of length 1.
• n = 3. Only 2: the answer is 1. The outer loop does not run (2 × 2 = 4 is not below 3).
• n is itself prime (n = 7). It is excluded: "strictly less than".
• n is a perfect square (n = 25). The loop runs while p × p < 25, so p stops at 4; 25 itself is out of range anyway.

Follow-ups

• "Return the primes, not the count." [k for k in range(n) if is_prime[k]].
• "n is 10¹⁰; the list does not fit in memory." Use a segmented sieve: sieve the primes up to √n once, then process [0, n) in blocks of, say, 10⁶, crossing off multiples of those small primes in each block. Memory is O(√n + block size).
• "Answer many queries: how many primes are ≤ x?" Sieve once up to the maximum x, build a prefix count, and answer each query in O(1).