Sieve of Eratosthenes — Generate All Primes Up to N in O(n log log n)

Problem Statement#

Given an integer n, return the number of prime numbers that are strictly less than n.

Constraints:

• 0 <= n <= 5 * 10^6

Input:  n = 10
Output: 4
Explanation: Primes less than 10 are [2, 3, 5, 7].

Input:  n = 0
Output: 0
Explanation: No primes less than 0.

Why This Problem Matters#

The Sieve of Eratosthenes is one of the oldest algorithms in existence (attributed to the Greek mathematician Eratosthenes around 240 BC) and remains one of the most practically useful. Google asks sieve-related problems because they test whether a candidate can reason about algorithmic efficiency at scale — trial division checking every number up to n takes O(n sqrt(n)) time, which times out for n = 5 * 10^6. The sieve reduces that to O(n log log n), a dramatic improvement.

More importantly, the sieve is foundational: prime factorization in O(log n), Euler's totient function, Mobius function, and smallest prime factor sieves all build on the same idea. Interviewers use LC 204 as a springboard to ask harder follow-ups involving number theory.

The Core Insight#

You do not need to check every divisor. If a number p is prime, then all its multiples — 2p, 3p, 4p, ... — are composite. Cross them out. Any number not crossed out by the time you reach it must itself be prime (no smaller prime divided it).

Two crucial optimizations:

1. Outer loop only up to sqrt(n). If p is prime and p * p > n, then all composites that p would mark have already been marked by smaller primes.

2. Inner loop starts at p * p. Multiples 2p, 3p, ..., (p-1)p were already marked by primes smaller than p.

This gives the sieve its near-linear performance: the harmonic series sum 1/2 + 1/3 + 1/5 + 1/7 + ... over all primes converges to log log n.

Visual Dry Run#

Sieve for n = 30, find all primes less than 30:

Remaining True indices: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 — that is 10 primes.

When p=5, multiples 10, 15, 20 were already marked by 2 and 3. Only 5*5=25 is a new mark.

Solution (Optimal)#

def countPrimes(n: int) -> int:
    if n < 2:
        return 0
 
    # bytearray: 1 byte per slot vs 28 bytes for Python int object
    is_prime = bytearray([1]) * n
    is_prime[0] = 0
    is_prime[1] = 0
 
    p = 2
    while p * p < n:               # only go up to sqrt(n-1)
        if is_prime[p]:
            for multiple in range(p * p, n, p):  # start at p*p, not 2p
                is_prime[multiple] = 0
        p += 1
 
    return sum(is_prime)            # sum of 1s = count of primes below n

function countPrimes(n) {
    if (n < 2) return 0;
 
    const isPrime = new Uint8Array(n).fill(1);  // 1 byte per element
    isPrime[0] = 0;
    isPrime[1] = 0;
 
    for (let p = 2; p * p < n; p++) {
        if (isPrime[p] === 1) {
            for (let multiple = p * p; multiple < n; multiple += p) {
                isPrime[multiple] = 0;  // mark composite
            }
        }
    }
 
    let count = 0;
    for (let i = 2; i < n; i++) {
        if (isPrime[i] === 1) count++;
    }
    return count;
}

Time: O(n log log n) — the inner loop total work sums to this via harmonic primes Space: O(n) — the boolean sieve array

Common Mistakes#

• Off-by-one on the boundary. LC 204 asks for primes strictly less than n. Count is_prime[2..n-1].
• Not starting the inner loop at p * p. Starting at 2 * p is still correct but twice as slow.
• Integer overflow with p * p. In C++/Java, p * p can overflow when p is near 70,000. Cast to long before the multiplication.
• Using Python lists instead of bytearray. Python list elements are 28 bytes each vs 1 byte in bytearray. For n = 5 * 10^6 this is the difference between 140 MB and 5 MB.
• Forgetting the edge case n <= 2. If n is 0, 1, or 2, the answer is 0.

Interview Tips#

• Immediately mention the bytearray / Uint8Array memory optimization — it signals systems awareness.
• Explain why the inner loop starts at p*p (all smaller multiples were marked by smaller primes).
• Offer the segmented sieve as a follow-up for memory-constrained large n.

Follow-up Questions#

• Find all primes in range [L, R] where R can be 10^12? Use a segmented sieve. Generate primes up to sqrt(R) with a standard sieve. Create a boolean array of size R-L+1 and mark composites using each small prime.
• How do you factorize every number from 1 to N in O(log n) each after preprocessing? Build the SPF (smallest prime factor) sieve. spf[i] stores the smallest prime dividing i. Factorize by repeatedly dividing by spf[n].
• Count primes in arbitrary intervals online? Build prefix sum array: prefix[i] = number of primes up to i. Then count(L, R) = prefix[R] - prefix[L-1] in O(1).
• Can you parallelize the sieve? Yes. Split [2, n] into blocks. Each thread processes one block, crossing out multiples of primes from [2, sqrt(n)].

Key Takeaways#

• The sieve transforms "is this number prime?" from O(sqrt(n)) per query into O(1) lookup after O(n log log n) preprocessing.
• The critical optimization: start marking composites at p*p, not 2p — everything smaller was already marked by smaller primes.
• Use bytearray in Python and Uint8Array in JavaScript for memory-efficient boolean arrays.
• The outer loop only needs to run up to sqrt(n) — beyond that, every composite has already been crossed out.
• The segmented sieve extends the idea to ranges [L, R] with O(sqrt(R)) space instead of O(R).
• The SPF sieve variant enables O(log n) factorization per number after the same O(n log log n) preprocessing.
• Whenever a problem needs primality for many numbers up to n, the sieve is almost always the right first tool.