Sieve of Eratosthenes — Watch Composites Vanish in Waves up to 200

Eratosthenes of Cyrene, working in Alexandria around 240 BCE, asked a practical question: how do you list every prime up to a given limit? His answer is one of the oldest algorithms still taught today. Write the numbers from 2 to N in a grid. Circle 2 (the first prime) and cross out every other multiple of 2. Circle the next surviving number — 3 — and cross out every other multiple of 3. Keep going. When you have processed every prime up to \sqrt{N}, the numbers still uncrossed are exactly the primes up to N.

Reading the rule is one thing. Watching it unfold is another. When you see the multiples of 2 vanish, then the multiples of 3, then 5 — each pass eating a thinner slice of what remains — you feel why the primes become rare. The sieve is not subtracting a few numbers. It is subtracting, at each stage, a regular arithmetic progression — and the survivors are whatever slips through every arithmetic net.

How the sieve works

Write the integers from 2 up to 200 in a grid. You will mark each number as either prime (kept) or composite (crossed).

Start with p = 2.
Mark p as prime.
Cross out 2p, 3p, 4p, \ldots (every multiple of p beyond p itself). These cannot be prime — they have p as a proper divisor.
Move p to the next uncrossed number above the current p.
Repeat from step 2 until p > \sqrt{N}.
Every uncrossed number at the end is prime.

The stopping condition p > \sqrt{N} deserves a line of its own. Why stop at \sqrt{N}: if a composite n \leq N had all its prime factors > \sqrt{N}, then n would be a product of two factors both larger than \sqrt{N} — so n > N, contradiction. Every composite \leq N has a prime factor \leq \sqrt{N}, so it must have been crossed out during one of the passes we already ran.

For N = 200, \sqrt{200} \approx 14.14. The primes up to 14 are 2, 3, 5, 7, 11, 13. Only six passes are needed to reveal every prime up to 200.

Step through the sieve

pass = 0:

Drag the slider through $6$ passes. Pass $0$: all $199$ candidates present. Pass $p$ crosses out multiples of the $p$-th prime that haven't already been crossed. By pass $6$ the sieve halts (next prime $17 > \sqrt{200}$) and $46$ primes survive.

The waves get thinner

Here is the thing the slider reveals that the description cannot. Pass 1 — multiples of 2 — eliminates 99 numbers. Pass 2 — multiples of 3 not already crossed — eliminates 32 more. Pass 3 eliminates 14. Pass 4 eliminates 5. Pass 5 eliminates 2 more. Pass 6 eliminates just 1. The waves get thinner because most of the multiples have already been eaten by earlier waves. 15 = 3 \times 5, for instance, was crossed out during pass 2 (as 3 \times 5); the pass for 5 never needed to visit it again.

This is why an efficient implementation starts crossing out multiples of p not at 2p but at p^2. Why: every multiple of p strictly below p^2 is also a multiple of some prime smaller than p, so it was already crossed during an earlier pass. For p = 11, the first new multiple to cross is 11^2 = 121; everything smaller (like 22, 33, 44, 55, 66, 77, 88, 99, 110) was crossed during passes 2 through 7.

Why the sieve is still fast

The sieve does roughly N (1/2 + 1/3 + 1/5 + 1/7 + \ldots) work — a sum over primes up to \sqrt{N}. By a classical estimate (Mertens' theorem), this sum grows like \ln \ln N, which is vanishingly slow. For N = 200, \ln \ln 200 \approx 1.66. For N a billion, it is about 3.2. Doubling N barely changes the work-per-number. This is why the sieve remains competitive for finding all primes up to a bound even today — modern implementations still use Eratosthenes' idea, just with hardware that can cross out a billion numbers a second.

Why the survivors must be prime

After the sieve finishes, is it guaranteed that every uncrossed number is prime? Yes. Suppose n \leq N survives the sieve. If n were composite, n = a \cdot b with 1 < a \leq b < n. Then a \leq \sqrt{n} \leq \sqrt{N}, so a is a prime-or-composite \leq \sqrt{N}. Every composite \leq \sqrt{N} itself has a prime factor \leq \sqrt{N}, so ultimately n has a prime factor p \leq \sqrt{N}. But we crossed out every multiple of every prime \leq \sqrt{N}. So n would have been crossed. Contradiction — n must be prime.

The sieve is therefore not just a recipe. It is a proof by construction: the survivors are primes, and the primes are exactly the survivors.

One more look

You have watched 199 candidates get sliced into 46 survivors in six passes. Those 46 numbers — 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199 — are the primes of the first two hundred integers. They are what remains when you remove everything that has structure. By the Fundamental Theorem of Arithmetic, they are also the atoms from which every one of the 154 composites was built.