Sieve of Eratosthenes

An ancient method that finds all primes up to n by iteratively marking multiples of each prime as composite.

How it works

The sieve of Eratosthenes lists integers from 2 to n and repeatedly takes the next unmarked number as prime, then marks all of its multiples as composite. When the process passes the square root of n, every remaining unmarked number is prime. It runs in O(n log log n) time and O(n) space, making it the standard way to enumerate small primes.

Why start at the square

Kronos motion — classical

When marking multiples of a prime p, all smaller multiples (2p, 3p, ... up to p*p) have already been marked by smaller primes, so marking can begin at p*p. This optimization, plus stopping the outer loop at sqrt(n), removes redundant work.

Implementation

python

def sieve(n):
    is_prime = bytearray([1]) * (n+1)
    is_prime[0] = is_prime[1] = 0
    p = 2
    while p*p <= n:
        if is_prime[p]:
            for m in range(p*p, n+1, p):
                is_prime[m] = 0
        p += 1
    return [i for i in range(2, n+1) if is_prime[i]]

Refinements

A linear sieve marks each composite exactly once, in O(n), while also recording smallest prime factors.
Segmented sieves process the range in cache-sized blocks to handle large n with limited memory.
Wheel factorization skips multiples of small primes to cut constant factors.
Storing smallest-prime-factor tables gives O(log n) factorization of any number up to n afterward.

Uses

Beyond listing primes, the sieve precomputes factorizations, Euler's totient, and Moebius values for number-theory problems. For testing a single large number, deterministic Miller-Rabin is faster; the sieve wins when you need all primes or many factorizations in a range.