The Sieve of Eratosthenes

How do you actually find every prime up to some limit? You could test each number one at a time — try dividing $91$ by $2, 3, 5, 7\dots$ — but that's slow, and you throw the work away after every single number. Eratosthenes, the chief librarian of the great Library of Alexandria (the same man who, without ever leaving Egypt, worked out the circumference of the whole Earth from two shadows), found a cleverer way around 200 BC. It needs no division at all — just systematic, mechanical crossing-out — and it is still, over two thousand years later, the fastest simple method known for listing primes.

The trick is to stop hunting for primes one by one, and instead find them all at once by sieving the composites away — striking out every number that isn't prime until only primes remain standing.

Eratosthenes was such an all-round scholar — geography, poetry, astronomy, athletics, maths — that his rivals in Alexandria nicknamed him "Beta," second-best at everything, never quite first at any one thing. History has been kinder: his circumference of the Earth was startlingly close to the true value, and his prime-finding trick is the one idea of his that every student still meets today, unchanged, twenty-two centuries on.

The method

Write out the numbers 2, 3, 4, \dots, N.
Circle the first un-struck number — it is prime. Strike out every larger multiple of it.
Move to the next un-struck number and repeat.

Whatever is never struck is prime. There is one beautiful shortcut worth knowing: you can stop once you pass \sqrt{N}. Any composite number n \le N has a factor no bigger than \sqrt{n} \le \sqrt{N}, so by the time you've processed every prime up to \sqrt{N}, every composite has already been struck at least once — there's nothing left to catch. Step through the sieve up to $60$ below and watch each prime take its turn.

Worked example: sieving 2 to 30 by hand

Let's do the whole thing on paper. Write out the numbers from $2$ to $30$, and work through them exactly as the rule says.

Circle $2$. It's the smallest un-struck number, so it's prime. Strike out every larger multiple of $2$: $4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30$ — every even number above $2$ is now gone.
Circle $3$. It survived the first pass, so it's prime. Strike out its larger multiples that are still standing: $9, 15, 21, 27$ (the even multiples $6, 12, 18, 24, 30$ were already struck by $2$).
Circle $5$. Still standing, so it's prime. Strike out $25$ — its only surviving larger multiple below $30$ ($10, 15, 20, 30$ were already gone).
Check the shortcut. $\sqrt{30} \approx 5.48$, and the very next prime is $7$, which is already bigger than that. So we can stop — every composite up to $30$ is guaranteed to have been struck already.
Circle everything left standing. That's $2, 3, 5, 7, 11, 13, 17, 19, 23, 29$ — ten primes below $30$, found without a single division.

Notice how little work that was: three primes ($2$, $3$, $5$) did all the striking, and together they cleared out every composite up to $30$ before we ever had to think about $7, 11$, or anything bigger.

Worked example: how far do you sieve for $N = 100$?

The shortcut gets more valuable the bigger $N$ gets. Suppose you want every prime up to $100$. Since \sqrt{100} = 10, you only ever need to circle-and-strike with the primes up to and including $10$ — that's just 2, 3, 5, 7. The next prime, $11$, has $11^2 = 121$, which already overshoots $100$, so by the time $7$ has finished striking, nothing composite could possibly be left un-struck.

Four primes — $2, 3, 5, 7$ — are enough to sift out every composite among the $99$ numbers from $2$ to $100$, leaving the $25$ primes below $100$ standing. Compare that to testing all $99$ numbers individually by trial division: the sieve does dramatically less work, because each prime strikes its own multiples exactly once instead of every number being checked against every possible divisor.

Counting the actual strikes makes the saving concrete. For $N = 100$:

$p = 2$ strikes $4, 6, 8, \dots, 100$ — that's $49$ strikes.
$p = 3$ strikes $9, 15, 21, \dots, 99$ (skipping anything $2$ already caught) — about $17$ more strikes.
$p = 5$ strikes the handful of surviving multiples of $5$ — about $7$ more.
$p = 7$ strikes just $49, 77, 91$ — its first few multiples were already gone.

Roughly $80$ strikes in total lay bare all $99$ numbers, and every single strike is a plain addition (jump to the next multiple) — never a division. Trial-dividing every one of the $99$ numbers by every smaller candidate divisor would take vastly more individual checks for the same answer.

Why it works

Every composite number has a smallest prime factor p, and the sieve strikes it out exactly when it processes that p. So no composite can survive. A prime, on the other hand, is a multiple of no smaller number, so nothing ever strikes it. The sieve is just the Fundamental Theorem of Arithmetic in action — every composite betrayed by its smallest prime factor.

Take $n = 91$. Its smallest prime factor is $7$, since $91 = 7 \times 13$. Sure enough, when the sieve reaches $p = 7$ and starts striking $14, 21, 28, \dots$, it eventually lands on $91 = 7 \times 13$ and crosses it out right there — even though $91$ survived the earlier passes of $2, 3$, and $5$ completely untouched, because none of them divide it. Every composite has exactly one first moment where its turn comes; the sieve never misses it, and never wastes a strike on a number that's already gone.

Almost everyone trips over one of these the first time they run the sieve:

Sieving all the way to $N$ instead of stopping at $\sqrt{N}$. It's tempting to keep circling-and-striking with every surviving number right up to $N$ itself. That still gives the correct list of primes, but it wastes enormous effort for nothing — once you pass \sqrt{N}, every remaining un-struck number is already guaranteed prime, because any composite that large would need a factor no bigger than \sqrt{N}, and every one of those has already done its striking.
Forgetting to strike out multiples of $2$ first. $2$ itself stays circled — it's prime — but every other even number ($4, 6, 8, \dots$) is composite and must go. Skip this first pass and half the grid is left un-struck, ruining every later count.

Remarkably, yes — and not just as a curiosity. Modern cryptography (the maths that keeps your banking and messaging apps secure) needs enormous prime numbers, hundreds of digits long, and finding them means testing huge random candidates for primality. A full primality test on a $600$-digit number is expensive — so before running one, real cryptographic software first runs a small trial-division sieve, instantly discarding any candidate divisible by $2$, $3$, $5$, $7$, and every other small prime.

Only the survivors of that quick, cheap sieve — Eratosthenes' exact idea, run on a silicon chip instead of a wax tablet — go on to the slow, expensive test. In fact the saving is huge: sieving candidates against the first few thousand small primes throws away the overwhelming majority of random numbers almost instantly, so the expensive test only ever runs on the small fraction that might actually be prime. A librarian's trick from ancient Alexandria is, quite literally, running inside your phone right now, every time it sets up a secure connection.