The Sieve of Eratosthenes
A 2,200-year-old algorithm for finding primes that's so simple a child can do it — and so clever it's still taught in every CS course.
Around 240 BC, a Greek polymath named Eratosthenes of Cyrene invented an algorithm so elegant that we still use it today, essentially unchanged. He also measured the circumference of the Earth using shadows and a stick (and got it roughly right), ran the Library of Alexandria, and was nicknamed “Beta” by his peers — supposedly because he was the second best at everything, but good at everything. Which, frankly, sounds like the best person to have at a dinner party.
His most enduring contribution to mathematics is a method for finding all prime numbers up to any given limit. It’s called the Sieve of Eratosthenes, and it works like a colander for composites: you pour in all the numbers and shake out the non-primes.
How It Works
The idea is almost comically simple:
- Write down all numbers from 2 to your limit (let’s use 100).
- Start at 2 — the first prime. Keep it. Now cross out every multiple of 2 (4, 6, 8, 10, …). Those are all composite.
- Move to 3 — the next uncrossed number. Keep it. Cross out every multiple of 3 (6, 9, 12, 15, …). Some are already crossed out — that’s fine, cross them again if you like. Nobody’s keeping score.
- Move to 5 (4 was already crossed out). Cross out multiples of 5 (10, 15, 20, 25, …).
- Move to 7. Cross out multiples of 7 (14, 21, 28, …).
- Stop. Why stop at 7? Because 7 is the largest prime whose square is less than or equal to 100 (7² = 49 ≤ 100, but 11² = 121 > 100). Any composite number up to 100 must have a factor no larger than √100 = 10, so by the time you’ve sieved through 2, 3, 5, and 7, every composite has been caught.
Every number still standing is prime.
The Grid
Here are the numbers 1–100 after running the sieve. 1 is neither prime nor composite (it’s in a category of its own), primes are highlighted, and everything else has been sieved out.
25 primes survive the sieve: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, and 97.
Why It’s Genius
The sieve doesn’t test each number individually (that’s slow). Instead, it works forward: once you know 2 is prime, you immediately eliminate half of all remaining candidates. Then 3 knocks out another third. By the time you reach 7, almost everything composite is already gone.
This is the difference between a sieve and trial division. Trial division asks: “Is 91 prime? Let me try dividing by 2, 3, 5, 7… oh, 91 = 7 x 13, nope.” The sieve never even looks at 91 — it got crossed off when we processed 7’s multiples. The sieve does the work once and reaps the benefits across the entire range.
For finding all primes up to a limit, the sieve is dramatically faster. Modern implementations can find every prime below one billion in under a second.
The Square Root Trick
Why did we stop sieving at 7? Here’s the insight: if a number n is composite, at least one of its factors must be ≤ √n. (If both factors were bigger than √n, their product would exceed n — a contradiction.)
So to sieve up to 100, you only need to process primes up to √100 = 10. The primes below 10 are 2, 3, 5, and 7. Four passes. That’s it. To sieve up to a million, you’d only need primes up to 1,000 — and there are just 168 of those.
This is why the sieve scales so well. The work grows slowly compared to the range.
What the Sieve Reveals
Stare at that grid for a moment and you’ll notice patterns:
- No even primes after 2. The entire second column (and fourth, sixth, eighth, tenth) is crossed out. Half the grid gone in one pass.
- No prime ends in 5 after 5. Any number ending in 5 (other than 5 itself) is divisible by 5.
- Primes cluster in certain columns. In a 10-wide grid, primes can only appear in columns ending in 1, 3, 7, or 9 (plus 2 and 5 in the first row). Six out of ten columns are dead zones.
- The gaps between primes get wider — but irregularly. Sometimes you get twin primes like (71, 73), and sometimes you wait from 89 all the way to 97.
These patterns hint at the deep structure hidden inside the primes — structure that mathematicians have spent centuries trying to fully understand.
Still Going Strong
The sieve of Eratosthenes is one of the oldest algorithms in existence and it is still useful. Variations of it (the segmented sieve, the sieve of Atkin, wheel factorization) power everything from cryptographic key generation to competitive programming contests.
Not bad for a method invented by a man whose peers thought he was only the second best at things.