intuition

How Eratosthenes catches every prime

2026-05-06

Primes feel like a separate species - 2, 3, 5, 7, 11, 13, 17, 19, 23 - showing up at uneven intervals, refusing to share their pattern. Where do they come from? Honest answer: you don't find primes. You sieve everything else out, and primes are the residue.

Lay out the first 100 numbers. Drag the slider one notch at a time.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
step
-

-

-

Step 1 catches every multiple of 2. Step 2, the multiples of 3. Step 3, multiples of 5. Step 4, multiples of 7. Four passes. The 25 numbers that nobody crossed out are the primes.

That's the whole algorithm. Eratosthenes wrote it down in the third century BC and there is still nothing better for finding every prime under a given bound. He also measured the circumference of the Earth, but that is for another post.

Why only four primes are enough

Look at the slider. It only goes up to 4. Nobody had to cross out the multiples of 11 or 13. Why?

Because every composite number under 100 has a factor under √100 = 10. If n = a·b and both a and b are above 10, then n is above 100. So at least one of n's factors is at most 10. That factor drags a prime factor along with it - and the primes up to 10 are exactly 2, 3, 5, 7.

So those four primes catch everyone composite under 100. The next prime is 11, and the smallest new composite it could catch on its own is 11·11 = 121 - which is already off the grid.

Why the colours stack

Each composite cell is tinted by the smallest prime that divides it. 15 is coloured by 3, not by 5, because 3 caught it first. 21 is coloured by 3, not by 7. 91 is coloured by 7, because nobody under 7 managed to.

That's why each pass catches fewer cells than the last. By the time prime 7 starts swinging, prime 2 has already taken half the grid, prime 3 has taken a third of what was left, and prime 5 has mopped up. 7 only gets three new ones: 49, 77, 91. The diminishing returns are the visual proof that the sieve terminates fast.

What's left

25 primes between 1 and 100. They're not a separate kind of number. They're the numbers that no smaller multiplication could reach.

Composites are the stretches you can build out of smaller numbers. Primes are the unstretchable atoms - the building blocks you can't build any other way. 15 is a 3 stretched by 5. 17 is just 17.

A sieve made of multiplication. Pour in the integers and only the primes survive.