The idea: cross out multiples, keep what is left
The Sieve of Eratosthenes lists every prime up to n without dividing anything. Write down 2 … n. The smallest number not crossed out is prime. Cross out its multiples, then move to the next number still standing. Whatever is never crossed out is prime.
On the canvas, each prime p gets its own colour. A crossed cell keeps the light colour of the first prime that crossed it, which is its smallest prime factor. Press Next Prime to run one pass, one cross-out per step, or Finish Sieve to run the rest (Demo 1: full sieve to 100).
Why a pass starts at p²
A multiple k·p with k < p has a prime factor smaller than p, so an earlier pass already crossed it. For p = 3, the multiple 6 = 2 × 3 is gone after pass 2, so pass 3 starts at 9 = 3². For p = 7, 14, 21, 28, 35 and 42 are all crossed already; pass 7 starts at 49 (Demo 2: one prime's pass).
Starting at p² does not remove every repeat. 12 is crossed by 2 and again by 3; 30 is crossed by 2, 3 and 5. Each of those is a repeat: it costs an operation and changes nothing. For n = 100 the four passes do 104 cross-outs, and 30 of them are repeats.
| p | crosses out | cross-outs |
|---|---|---|
| 2 | 4, 6, 8, … 100 | 49 |
| 3 | 9, 12, 15, … 99 | 31 |
| 5 | 25, 30, 35, … 100 | 16 |
| 7 | 49, 56, 63, … 98 | 8 |
Why the sieve stops at √n
If k ≤ n is composite, write it as k = a × b with a ≤ b. Then a × a ≤ k ≤ n, so a ≤ √n. Every composite up to n therefore has a prime factor no bigger than √n, and the pass for that factor crosses it out. For n = 100, √n = 10: after the passes for 2, 3, 5 and 7, the next open number is 11, and 11² = 121 > 100. Every number still open is prime, and the sieve stops (Demo 3: stop at √n).
With n = 30, √30 ≈ 5.48, so only 2, 3 and 5 need passes: 24 cross-outs, 5 of them repeats, and 10 primes. 7 is prime but needs no pass, because 7² = 49 > 30 (Demo 5: a smaller n).
Counting the work: sieve vs trial division
Trial division tests one number k by dividing it by 2, 3, …, ⌊√k⌋ and stopping at the first divisor. 91 takes 6 divisions to find 7; the prime 97 takes 8 divisions to find nothing. Doing it for every k from 2 to 100 costs 236 divisions; the sieve needs 104 cross-outs, each just an addition and a write (Demo 4: count the work).
| n | sieve cross-outs | trial divisions (2 … n) | ratio |
|---|---|---|---|
| 100 | 104 | 236 | 2.3× |
| 1,000 | 1,411 | 5,288 | 3.7× |
| 10,000 | 16,981 | 117,527 | 6.9× |
| 1,000,000 | 2,122,048 | 67,740,404 | 32× |
The sieve does about n · ln ln n work: pass p costs about n/p, and the sum of 1/p over primes up to √n grows like ln ln n. Trial division over the whole range grows like n√n / ln n, because each prime k needs about √k divisions. The sieve's price is memory: one bit or byte per number up to n. To test a single large number, trial division or a probabilistic test (see Modular Exponentiation) is the right tool; to list all primes up to n, the sieve is. See Big-O Growth for how these curves pull apart, and Euclid's GCD for another algorithm from Euclid's era that avoids factoring.
Prime Factorization splits a number into these primes with a factor tree and shows the leaves are always the same.
Write the numbers in a square spiral and mark the primes the sieve finds, and they line up on diagonals: see The Ulam Spiral: Primes on Diagonals.
What the page leaves out
Real sieves store one bit per odd number only (half the memory), cross out with step 2p, and use a segmented sieve that works on cache-sized blocks to reach n = 109 and beyond. The linear sieve (Euler's) crosses each composite exactly once, and the sieve of Atkin uses quadratic forms; both are faster in theory, rarely in practice.