The Sieve of Eratosthenes: Finding Every Prime Without Dividing Once

Cross off the multiples, keep what survives

The Sieve of Eratosthenes, devised by the Greek mathematician around 240 BC, finds every prime up to a limit N without ever testing divisibility on a single candidate number one at a time. Instead it writes down every integer from 2 to N, then repeatedly takes the smallest number not yet crossed out and crosses out all its multiples. Whatever survives the whole pass — never crossed out — is prime, by construction: a composite number always has a smallest prime factor, and that factor's own sweep is guaranteed to catch it.

for p from 2 to N:
    if p is not marked:            # p survived every earlier sweep → prime
        for multiple m = p*p, p*p+p, p*p+2p, ... ≤ N:
            mark m as composite
# everything unmarked is prime

The one optimisation that matters is starting each sweep at p² rather than 2p. Every composite smaller than p² that is a multiple of p must also be a multiple of some prime smaller than p, so it was already crossed out by an earlier sweep — starting at p² skips redundant work without missing anything.

Why it stops at √N

You only need to sweep with primes up to √N. Any composite number m ≤ N has at least one factor ≤ √m ≤ √N, so if m has survived every sweep by a prime up to √N, it cannot be composite — it must be prime. This single fact turns an O(N) scan of "primes to check" into an O(√N) one, and it is the whole reason the sieve is fast: for N = 10,000 you only need to sweep with the 25 primes up to 100.

Complexity: better than testing each number alone

Trial division on every number up to N individually costs roughly O(N√N). The sieve instead spends O(N log log N) total work — for each prime p up to √N it marks about N/p multiples, and the sum 1/2 + 1/3 + 1/5 + 1/7 + ... over primes converges (very slowly) to log log N by Mertens' second theorem. In practice this means the sieve finds all primes below ten million in a fraction of a second, something trial division could never do at that speed.

work ≈ N · ( sum of 1/p for primes p ≤ √N )
        ≈ N · log(log(√N))
        =  O(N log log N)

Prime gaps and the counting function π(x)

Once the sieve has run, two questions become easy to explore visually. π(x), the prime-counting function, just counts how many primes are ≤ x — reading it straight off the sieve's surviving cells. The prime number theorem says π(x) is approximately x / ln(x) for large x, meaning primes near x are spaced roughly ln(x) apart on average — sparser and sparser the further out you look, even though there are always infinitely more to find (a fact Euclid proved by contradiction over two thousand years ago). Prime gaps — the distance between consecutive primes — are what the sieve makes visually obvious: short near the start (2,3,5,7 are packed tight), stretching out on average, but with no known largest gap and occasional dramatic outliers.

Wheel factorisation: sieving faster still

A simple further speed-up is to skip even numbers entirely — after 2, no even number is prime, so a sieve can allocate memory only for odd numbers and halve both the memory and the work. Extending the same idea to skip multiples of 2, 3 and 5 too (a "wheel" of period 30) removes roughly 73% of composites before the main sieve even starts, at the cost of a slightly fiddlier indexing scheme. Segmented sieving — processing N in blocks that fit in cache — is the other standard production trick, letting the algorithm scale to billions without exhausting memory.

Frequently asked questions

Try it live

Everything above runs in your browser — open Prime Sieve and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.