What Is the Prime Sieve? The Algorithm Behind Count Primes

You have an interview. They ask you to find all primes up to N. Your first instinct is to loop from 2 to N and test each number individually. You feel good about it. Then you hit the submit button and watch your O(n√n) solution achieve a spectacular time limit exceeded at N = 5,000,000.

The Sieve of Eratosthenes solves the exact same problem in O(n log log n) with a single array sweep, and a Greek mathematician figured this out in roughly 240 BC. So there's no excuse.

This guide explains how the sieve works, why the inner loop starts where it does (this is the question interviewers are waiting to ask), and which interview problems actually use it.

The Naive Approach Is Quietly Brutal

The obvious approach: for each number from 2 to N, check divisibility up to its square root. That's O(√n) per number. Do it N times and you land at roughly O(n√n).

At N = 5,000,000 (the constraint on LeetCode 204), that's about 11 billion operations.

You will time out. Your computer will not catch fire, but you will time out.

The sieve flips the approach entirely: instead of asking "is this number prime?", it asks "which numbers does this prime eliminate?"

That one shift in perspective is what makes the whole thing work.

Think in Eliminations, Not Tests

Imagine a list of every integer from 2 to N, all marked "possibly prime." This is your starting state. Everyone is innocent until proven a multiple of something smaller.

Start at 2. It's still marked, so it's prime. Cross out every multiple of 2: 4, 6, 8, 10, and so on. You're not checking anything. You're marking consequences.

Move to 3. Still marked. Cross out 9, 12, 15... (6 was already crossed out by 2, but double-marking is fine).

Move to 4. Already crossed out. Skip it entirely.

Move to 5. Still marked. Cross out 25, 30, 35...

Keep going until you've processed everything up to √N. Whatever is still marked at the end is prime.

Each number gets crossed out by its smallest prime factor, so the total work is far less than testing every number independently.

Watching It Work: Primes Up to 30

Start with 2 through 30, all assumed prime.

Pass p=2: Mark 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30 as composite.

Pass p=3: Mark 9, 15, 21, 27 as composite. (12, 18, 24, 30 were already handled by 2.)

Pass p=5: Mark 25 as composite. (30 was already marked.)

Pass p=7: 7² = 49 > 30. Stop.

What's left: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29. Every prime up to 30, found with a handful of passes instead of 29 individual tests.

Why Does the Inner Loop Start at p², Not 2p?

This is the question. Every interviewer who knows this algorithm will ask it. Most candidates say "it's an optimization" and leave it there. That's not a complete answer.

Any multiple of p smaller than p² has already been marked by a smaller prime.

Take p = 5. The multiples are 10, 15, 20, 25, 30...

10 = 5 × 2. Marked when we processed p=2.
15 = 5 × 3. Marked when we processed p=3.
20 = 5 × 4. Marked by p=2.
25 = 5 × 5. First multiple not previously marked. This is where the useful work starts.

Starting at p² isn't just an optimization you toss in at the end to look smart. Starting at 2p means every single pass is wasting time re-marking things. The first genuinely new mark for any prime p is always p².

A side effect: the outer loop only needs to run to √N. Once p > √N, p² > N, and there's nothing left to mark. You can stop early.

The Prime Sieve Algorithm in Code

def count_primes(n: int) -> int:
    if n < 2:
        return 0
    
    is_prime = [True] * n
    is_prime[0] = is_prime[1] = False
    
    p = 2
    while p * p < n:
        if is_prime[p]:
            for multiple in range(p * p, n, p):
                is_prime[multiple] = False
        p += 1
    
    return sum(is_prime)

function countPrimes(n: number): number {
    if (n < 2) return 0;
    
    const isPrime = new Array(n).fill(true);
    isPrime[0] = isPrime[1] = false;
    
    for (let p = 2; p * p < n; p++) {
        if (isPrime[p]) {
            for (let multiple = p * p; multiple < n; multiple += p) {
                isPrime[multiple] = false;
            }
        }
    }
    
    return isPrime.filter(Boolean).length;
}

public int countPrimes(int n) {
    if (n < 2) return 0;
    
    boolean[] isPrime = new boolean[n];
    Arrays.fill(isPrime, true);
    isPrime[0] = isPrime[1] = false;
    
    for (int p = 2; (long) p * p < n; p++) {
        if (isPrime[p]) {
            for (int multiple = p * p; multiple < n; multiple += p) {
                isPrime[multiple] = false;
            }
        }
    }
    
    int count = 0;
    for (boolean prime : isPrime) {
        if (prime) count++;
    }
    return count;
}

Two things worth noting. The outer loop condition is p * p < n, not p < n. And in Java, if p is large, p * p silently overflows a 32-bit int and gives you a nonsense negative number. Cast to long before the multiplication. The (long) p * p is doing real work, not just being verbose for fun.

Why O(n log log n) Is Basically Linear

Space is O(n). You allocate a boolean array of size n and nothing else. For a refresher on what that actually measures, see What Is Space Complexity?.

The time bound takes more work to see. If Big-O notation is unfamiliar, worth a quick detour before continuing.

The outer loop runs over all primes p ≤ √N. For each prime p, the inner loop does n/p iterations. Total work:

n × (1/2 + 1/3 + 1/5 + 1/7 + 1/11 + ...)

That sum (the reciprocals of all primes up to N) grows as log log N. Mertens proved this in 1874, which means this complexity result is older than the light bulb.

At n = 10⁶, log log n is about 2.9. At n = 10⁹, it's about 3.4. The runtime barely flinches as n gets enormous.

Compare that to O(n√n): at n = 10⁶, √n = 1000. The sieve wins by roughly two orders of magnitude, which is the kind of gap that separates "passes" from "times out."

Where Interviewers Actually Use It

The canonical problem is LeetCode 204: Count Primes. Given n, return the number of primes strictly less than n. The constraint goes up to 5 × 10⁶, which is the sieve's jurisdiction.

But the sieve is rarely the whole problem in a real interview. It's preprocessing for something harder. A few patterns that come up:

Precompute, then answer queries. Need to answer "is X prime?" for many different values of X up to N? Run the sieve once, answer each query in O(1). This is the "here's a lookup table, now solve the real problem" pattern.

Smallest prime factor table. A small variation lets you precompute the smallest prime factor (SPF) of every integer from 2 to N. Factorizing any number k then takes O(log k): divide repeatedly by spf[k] until you reach 1.

def build_spf(n: int) -> list[int]:
    spf = list(range(n + 1))
    p = 2
    while p * p <= n:
        if spf[p] == p:  # p is still prime
            for multiple in range(p * p, n + 1, p):
                if spf[multiple] == multiple:
                    spf[multiple] = p
        p += 1
    return spf

Counting primes in a range. Need all primes between L and R where R is huge but R - L is manageable? The segmented sieve handles this in O((R - L) log log R) time and O(√R) space. It sieves small primes up to √R first, then uses them to mark composites in the [L, R] window. Useful when R is in the billions and a full sieve would need gigabytes.

When the Sieve Is the Wrong Tool

The sieve allocates an array of size n. If you want to check whether a single large number like 10¹² is prime, you'd need a terabyte of memory. That's not a trade-off. That's just wrong.

For a single primality check, trial division up to √n is correct. It's O(√n) time and O(1) space. At n = 10¹², that's 10⁶ iterations. Finishes in milliseconds, no array required.

Rough rule: if N ≤ 10⁷ and you need many primes, sieve. If you need to check one large number, trial divide.

There's also a linear sieve that achieves true O(n) by marking each composite exactly once. In practice the constant factor is worse than the standard sieve for typical interview constraints, and explaining it at a whiteboard takes a while. The standard sieve handles 99% of what actually comes up.

The Two Mistakes That Get Marked Down

Starting the inner loop at 2p. The output is still correct. The problem is redundant work on every pass, and interviewers who know this algorithm notice immediately. The correct start is p².

Missing the edge case guard. For n ≤ 2, there are no primes strictly less than n. An unguarded array access on a size-0 or size-1 array crashes or silently returns garbage depending on the language. Guard at the top of the function. It's one line and it is embarrassing to miss.

For a full walkthrough with all 14 language variants, see the Sieve of Eratosthenes deep dive.

If you want to practice explaining algorithm choices out loud under pressure, SpaceComplexity runs voice-based mock interviews where you walk through problems exactly the way an interviewer expects: clarify constraints, state the approach, explain the complexity, and handle follow-ups.