The Sieve of Eratosthenes, Explained

After reading this you can run the oldest prime-finding algorithm by hand, predict exactly which cells survive, count the crossing-out work it costs, and read the diagonal stripes the multiples make in a grid.

What the sieve does

The Sieve of Eratosthenes lists every prime up to some limit N by removing composites instead of testing numbers one at a time. Write the integers from 2 to N. Take the smallest number not yet crossed out, call it prime, then cross out all of its multiples. Repeat. The numbers that survive are exactly the primes.

Here is the hook. To find every prime up to 30 you only ever cross out multiples of 2, 3, and 5. That is three passes. After you strike out multiples of 5, everything left standing (7, 11, 13, 17, 19, 23, 29 and the earlier survivors) is prime, and you never had to divide anything. The sieve replaces division with the far cheaper act of counting up in steps.

Why does it work? Every composite number has a prime factor, so when you reach the smallest such factor you cross the composite out as one of its multiples. Nothing composite can slip through. Nothing prime is ever crossed, because a prime has no smaller factor to cross it. The survivors are precisely the primes.

When to use it, and when not to

The sieve shines when you want all primes up to a fixed limit. For N in the millions it is fast and simple, and it needs only one bit of memory per number. That makes it the standard first step whenever a program needs a table of small primes.

It is the wrong tool for a single large number. To test whether one specific 200-digit number is prime, you would never build a table with 10^{200} entries. That job belongs to probabilistic tests like Miller-Rabin. The sieve is a bulk producer, not a spot-checker.

The stopping rule and the count of work

You can stop early. Once the current prime p satisfies p^2 \gt N, every remaining uncrossed number is already prime. The reason is short: any composite c \le N has a prime factor no larger than \sqrt{N}, so it was crossed on some earlier pass.

Here p is the prime you are currently processing and N is the top of your list. For N = 30 you have \sqrt{30} \approx 5.48, so you stop after crossing multiples of 5. The primes 7 through 29 fall out for free.

The total crossing-out work is the sum, over each prime p, of how many multiples of p lie in range, which is about N/p each. Summing gives a clean estimate.

The left side counts the strikes: N/p multiples for each prime p. The right side uses the fact that the sum of 1/p over primes up to N grows like \ln \ln N. That double logarithm grows painfully slowly. For N = 10^6, \ln \ln N \approx 2.63, so the sieve does roughly 2.6 million strikes to find all 78498 primes below a million.

A worked run to 30

Reading the diagonal stripes

Lay the numbers in a grid of fixed width w and the multiples of a prime p form a lattice. A multiple of p sits p steps to the right of the previous one. In a grid of width w, stepping right by p means moving p \bmod w columns over and wrapping down. When w is a multiple of p, the step lands in the same column each time, so you see straight vertical bands. Otherwise the marks slant into diagonals.

Width 6 is the instructive case. Every multiple of 2 lands in columns 2, 4, 6, and every multiple of 3 in columns 3 and 6. That leaves only columns 1 and 5 clean, which is the statement that every prime past 3 has the form 6k \pm 1. The grid makes an algebraic fact visible.

How the work thins out

The bar chart above shows a pattern that holds at every scale: the small primes carry the load. Multiples of 2 alone remove half the numbers. Multiples of 3 among the rest remove a third of those, and so on. The count of survivors after sieving with the first few primes follows the product below.

Here S estimates how many numbers survive after crossing multiples of every prime p up to a bound B, starting from N candidates. For N = 30 sieved by 2, 3, 5 you get 30 \cdot \frac{1}{2} \cdot \frac{2}{3} \cdot \frac{4}{5} = 8, close to the 10 primes actually found (the estimate ignores that 2, 3, 5 themselves survive). This product is the seed of Mertens' theorem and the prime number theorem's density estimate.

Common mistakes

Three errors trip people up when they code or hand-run the sieve.

Starting the strikes at the wrong place

When processing prime p, begin crossing at p^2, not at 2p. Every smaller multiple of p, such as 2p or 3p, already carries a smaller prime factor and was struck earlier. Starting at p^2 avoids repeat work.

Testing primality by division inside the sieve

The whole point is to avoid division. You never ask "is 91 prime?" You simply notice 91 was crossed when you processed 7. If a cell is still standing when you reach it, it is prime by construction.

Ignoring the stopping rule

Crossing multiples of primes above \sqrt{N} wastes time and finds nothing new. For a sieve to a million, you stop after 997, the largest prime below 1000, even though there are 78498 primes in total.

Related tools

Once you have the primes, the patterns are worth chasing. The Ulam Prime Spiral takes the same integers, coils them outward and marks the primes, and the diagonal streaks that appear echo the grid stripes here. The Goldbach Comet asks how each even number splits into two of your primes. For the machinery behind divisibility, the Euclidean Algorithm Visualizer shows greatest common divisors as tiled squares, and Modular Times Table and Pascal's Triangle mod n both turn remainders into pictures. If the grid-of-cells idea appeals, Conway's Game of Life and Elementary Cellular Automata run rules across grids of their own.

Related tools

3D Geometry Board

Points, lines, planes, spheres and polyhedra on an orbiting camera — slice solids with planes, unfold nets, drop the Dandelin spheres into a cone and drag everything.

Bézier Curve Playground

Drag control points and watch De Casteljau’s algorithm construct a Bézier curve step by step.

Central Limit Theorem Demo

Sample from any lopsided distribution and watch the averages pile up into a bell curve.

Conway’s Game of Life

Paint cells and watch Conway’s cellular automaton breed gliders, guns and oscillators.

Dynamic Geometry Board

Construct with points, lines, circles and transformations, then drag anything — the construction stays true, and a checker tells you which relations are theorems.

Fantasy Map Generator

Roll a seed and get a continent: coastlines, mountains, rivers, biomes and named towns, ready for your campaign.