Sieve of Eratosthenes: Find Every Prime Up to N in O(n log log n)

Around 240 BC, a Greek mathematician, geographer, and librarian named Eratosthenes described a procedure for finding every prime up to some limit. Cross off every composite by marking multiples. Keep every survivor. The survivors are prime.

That description is still the algorithm. Not a historical curiosity, not a teaching toy. The actual thing you reach for in 2026 when someone hands you a batch primality problem. Two thousand, two hundred years of number theory, and the basic structure for "give me all primes up to n" hasn't been beaten for practical use. If your problem needs primality information about many numbers in a range, you build the sieve once, pay O(n log log n), and every subsequent check is a single array lookup.

The mental model: the sieve is a boolean array that you mark up once, then query forever.

How the Crossing-Off Works

You allocate a boolean array is_prime[0..n], set every entry to true, then mark is_prime[0] and is_prime[1] as false (neither qualifies). Then you iterate:

for p from 2 to √n:
    if is_prime[p]:              # p survived, so it is prime
        for k from p*p to n, step p:
            is_prime[k] = false  # k is composite

Five lines. No primality tests, no modular arithmetic, no division anywhere. Just setting booleans to false.

After this loop, every index i where is_prime[i] is still true is prime. The structure never tests divisibility directly. It works by elimination.

Integers 2-30 after the full sieve. Blue = prime survivor. Line color shows which prime did the marking: amber for p=2, green for p=3, pink for p=5. The outer loop stops at √30 ≈ 5.47, so only p=2, 3, 5 need processing. Every prime up to 30, found with zero primality tests.

Two Optimizations Built Into the Algorithm

Neither of these is a micro-optimization. Both are structural properties that make the algorithm correct and efficient.

Why the outer loop stops at √n

Any composite number c has at least one prime factor p ≤ √c. Proof: if every prime factor were greater than √c, their product would exceed √c × √c = c, contradiction. So by the time you have processed every prime up to √n, every composite ≤ n has been marked by one of its factors. Nothing above √n needs to be processed.

Why the inner loop starts at p², not 2p

When you reach prime p in the outer loop, every multiple kp with k < p was already marked during the processing of an earlier prime. Why? If k < p, then k has a prime factor q ≤ k < p. When q was processed, it marked every multiple of q, including q(p*(k/q)) = k*p. Starting at p² is not a heuristic. The first potentially unmarked multiple of p is exactly p², and every earlier one was already handled.

When p=5, multiples 10, 15, and 20 are already gone. The inner loop starts at exactly 25 = 5×5. This isn't an optimization layered on top. It's how the algorithm is defined.

Core Operations

Amortize the build cost over m primality queries and the per-query cost approaches zero. After the first call, each subsequent isPrime(k) costs exactly one memory access.

Why O(n log log n) and Not O(n log n)

Most explanations wave at a formula and move on. Let's not.

The total number of marking operations equals:

n/2 + n/3 + n/5 + n/7 + n/11 + ...
= n × (1/2 + 1/3 + 1/5 + 1/7 + 1/11 + ...)
= n × Σ_{p prime, p ≤ n} 1/p

So the question is: how fast does the sum of prime reciprocals grow?

Compare it to the harmonic series: Σ 1/k ≈ ln(n). That sum covers every positive integer. The prime reciprocal sum covers only the primes, which thin out as numbers grow. By the prime number theorem, the density of primes near x is approximately 1/ln(x), meaning there are about n/ln(n) primes up to n. That thinning is why the sum grows as ln(ln(n)) instead of ln(n): you are summing a sequence that gets sparser at exactly the rate that collapses a logarithm into a double logarithm.

More precisely, if you model each term as roughly 1/(k ln k) for the kth prime:

Σ 1/(k ln k) ≈ ∫ dk / (k ln k) = ln(ln(k))

Mertens' second theorem (1874) formalizes this exactly:

Σ_{p ≤ n} 1/p = ln(ln(n)) + M + O(1/ln(n))

where M ≈ 0.2615 is the Meissel-Mertens constant. Substituting back:

total work = n × (ln(ln(n)) + M + O(1/ln(n))) = O(n log log n)

Diagram: How Slowly ln(ln(n)) Grows

n = 10^2:    ln(ln(100))     ≈ 1.53
n = 10^4:    ln(ln(10000))   ≈ 2.30
n = 10^6:    ln(ln(10^6))    ≈ 2.97
n = 10^9:    ln(ln(10^9))    ≈ 3.37
n = 10^12:   ln(ln(10^12))   ≈ 3.67

For n = 10^9, the sieve performs roughly 3n total marking operations. That's almost indistinguishable from linear.

The Overflow Bug You Will Almost Certainly Write

Here's the most common subtle error in sieve implementations. When computing the inner loop start, you write:

for (int multiple = p * p; multiple <= n; multiple += p)

If p is an int and p ≈ 46,341, then p * p ≈ 2.15 × 10^9, which overflows a 32-bit signed integer (max value 2,147,483,647). The result wraps to a negative number. The condition multiple <= n is true immediately (negative < any reasonable n), and you either walk off the start of the array or mark incorrect positions.

The fix is to widen the type before multiplying, not after. (long)(p * p) is too late: the multiplication already overflowed. You need (long)p * p.

// Java
for (int p = 2; (long) p * p <= n; p++) { ... }

// C++
for (int p = 2; (long long)p * p <= n; p++) { ... }

// Kotlin
while (p.toLong() * p <= n) { ... }

Python, Ruby, and Go are overflow-safe by default (Python integers are arbitrary precision; Go's int is 64-bit on 64-bit platforms). Every other language needs the explicit cast when n can approach or exceed 2^31.

A variant of this bug lived undetected in Java's Arrays.binarySearch for nine years before Joshua Bloch found it in 2006 while preparing a talk. So when you write it, you're in good company. But please fix it.

Cast before multiplying. (long) p * p promotes p to 64-bit first. (long)(p * p) casts the already-overflowed result, which is useless.

The Smallest Prime Factor Variant

The vanilla sieve is binary: prime or not. The smallest prime factor (SPF) sieve records the smallest prime dividing every number up to n. With it, you can factorize any number k ≤ n in O(log k) by repeatedly dividing by spf[k].

Build: initialize spf[i] = i for all i. For each prime p, iterate over its multiples and write spf[multiple] = p only if spf[multiple] == multiple, meaning no smaller prime has claimed it yet.

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

def factorize(n: int, spf: list[int]) -> list[int]:
    factors = []
    while n > 1:
        factors.append(spf[n])
        n //= spf[n]
    return factors

With SPF, a single O(n log log n) setup enables O(log k) factorization of any k ≤ n. Problems that ask you to factorize every integer in [1, n] drop from O(n√n) naive to O(n log log n + n log n) with SPF.

Segmented Sieve: When O(n) Memory Is Too Much

The plain sieve allocates O(n) space. For n = 10^8, a byte array runs 100 MB. For n = 10^9, that's 1 GB. Your CPU's L1 cache is about 32 KB. That's the whole tension, and this is the whole solution.

The segmented sieve solves this. First, compute all primes up to √n with the plain sieve. Then process the range [2, n] in blocks of size Δ ≈ √n. For each block [lo, hi], allocate a local boolean array of size Δ and mark the multiples of each small prime that fall inside the block.

Each block fits in L1 cache (~32 KB), so the constant factor improves dramatically even though the asymptotic complexity is unchanged. Time stays O(n log log n). Memory drops to O(√n + Δ) = O(√n). For n = 10^9, that's about 32 KB instead of 1 GB.

Phase 1 builds the small primes once. Phase 2 sweeps the full range in cache-sized chunks, reusing the same local array for each block. Memory stays O(√n) regardless of n.

One Structure, Every Language

Each implementation below produces a boolean array is_prime where is_prime[i] is true if and only if i is prime, for all i in [0, n]. The inner loop starts at p*p. Overflow guards are applied in languages with fixed-width integer arithmetic.

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

def primes_up_to(n: int) -> list[int]:
    return [i for i, v in enumerate(sieve(n)) if v]

What Problems It Solves

The sieve is the right tool any time you need prime information about a range of numbers, not just a single number.

Specifically:

• Counting primes up to n. Build the sieve, count the true entries.
• Batch primality testing. If you will test primality for many values in [1, n], pay the O(n log log n) upfront and answer each query in O(1).
• Enumerating primes in a range [a, b]. Build the sieve up to b, scan from a.
• Fast factorization of all numbers up to n. Use the SPF variant. Factor any k ≤ n in O(log k) after the build.
• Problems about prime properties. Twin prime pairs, prime gaps, Goldbach verification, numbers with exactly k distinct prime factors. All require the same underlying sieve.
• Generating prime-dependent sequences. Euler's totient function, Möbius function, and divisor sums can all be computed for every number up to n in one linear sweep, using the primes the sieve provides.

When to Use the Sieve of Eratosthenes

The signal is multiple prime queries over a bounded range, not a single isolated primality test.

Trial division for a single "is k prime?" question is perfectly fine. O(√k) per check, done in milliseconds. A million such questions on values up to n = 10^6 would take O(n√n) = O(10^9) operations with trial division. That's an afternoon. The sieve costs O(n log log n), roughly 3n, for the same task. The crossover where sieve wins happens much earlier than you'd expect from the formula alone.

Concrete signals:

• The constraint block says n ≤ 10^6 or 10^7, and the problem involves any kind of primality filtering across that range.
• The problem asks you to count, enumerate, or find primes in an interval.
• You see "smallest prime factor" or "prime factorization" for many numbers.
• The problem involves iterating over numbers and checking divisibility by primes.

Worked Example 1: Count Primes (LeetCode 204)

Problem: Given an integer n, return the number of prime numbers strictly less than n.

Naive approach: For each candidate k from 2 to n-1, run trial division up to √k. Each check costs O(√k), so total is O(n√n). For n = 5×10^6, that's about 3.5×10^9 operations. Way too slow.

Why the sieve fits: You need primality information for every number from 2 to n-1. That's exactly the "bounded range, many queries" pattern. Build the sieve once, count true entries. LeetCode 204 is, pleasantly, almost a direct translation of the algorithm. It's rare that "build the data structure the textbook describes" is the complete and correct solution.

def countPrimes(n: int) -> int:
    if n < 2:
        return 0
    is_prime = [True] * n    # indices 0..n-1
    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)

Time: O(n log log n). Space: O(n). For n = 5×10^6 this runs in milliseconds.

Worked Example 2: Closest Prime Numbers in Range (LeetCode 2523)

Problem: Given integers left and right (1 ≤ left ≤ right ≤ 10^6), find two primes p1 < p2 in [left, right] such that p2 - p1 is minimized. Return [-1, -1] if fewer than two primes exist in the range.

Naive approach: For each number in [left, right], run trial division. The range can have up to 10^6 values, each costing up to O(√10^6) = O(1000). That's up to 10^9 operations in the worst case.

Why the sieve fits: The range is bounded by right ≤ 10^6. You need all primes in [left, right], not just one. Build the sieve up to right once, collect the primes in the range, then scan adjacent pairs to find the minimum gap.

def closestPrimes(left: int, right: int) -> list[int]:
    is_prime = [True] * (right + 1)
    is_prime[0] = is_prime[1] = False
    p = 2
    while p * p <= right:
        if is_prime[p]:
            for multiple in range(p * p, right + 1, p):
                is_prime[multiple] = False
        p += 1

    primes_in_range = [i for i in range(left, right + 1) if is_prime[i]]

    if len(primes_in_range) < 2:
        return [-1, -1]

    best_gap = float('inf')
    result = [-1, -1]
    for i in range(1, len(primes_in_range)):
        gap = primes_in_range[i] - primes_in_range[i - 1]
        if gap < best_gap:
            best_gap = gap
            result = [primes_in_range[i - 1], primes_in_range[i]]

    return result

Time: O(right × log(log(right))) for the sieve, O(right - left) for the scan. Space: O(right).

The key insight: you sieve the entire range up to right, not just [left, right], because the sieve requires starting from 2. The segment [left, right] is then a trivial linear scan.

Recap

• Core idea: mark all composites by iterating over multiples of each prime. Survivors are prime.
• Outer loop stops at √n because every composite has a factor ≤ √n.
• Inner loop starts at p² because all smaller multiples of p were already marked by earlier primes.
• Time: O(n log log n) because total work = n × Σ(1/p) ≈ n × ln(ln(n)) by Mertens' second theorem.
• Space: O(n) for the boolean array. Segmented sieve reduces this to O(√n).
• Overflow trap: p * p overflows 32-bit int for p ≈ 46,341. Cast to 64-bit before multiplying in Java, C, C++, Kotlin, and C#.
• SPF variant records the smallest prime factor of every number, enabling O(log k) factorization after one O(n log log n) build.
• Reach for the sieve when you need primality information for many numbers in a bounded range, not for a single isolated check.

If you want to practice applying the sieve (and other DSA patterns) in actual timed interview conditions with real-time voice feedback, SpaceComplexity runs realistic mock interviews that mirror the pace and pressure of the real thing.

For understanding the complexity notation discussed here, see the guide to Big-O notation and how to read any loop. For a look at hash sets as the naive alternative for primality testing, see hash set time complexity.

Further Reading

• Sieve of Eratosthenes, Wikipedia
• Sieve of Eratosthenes, cp-algorithms.com (includes segmented and linear variants)
• How is the time complexity of Sieve of Eratosthenes O(n log log n)?, GeeksforGeeks
• Segmented Sieve, GeeksforGeeks
• Mertens' theorems, Wikipedia
• Linear Sieve, cp-algorithms.com