Sieve of Eratosthenes
Erase multiples instead of testing divisibility
Checking each number for primality on its own repeats the same divisions over and over. The sieve inverts that: assume everything is prime, then let each prime it confirms erase its own multiples in one sweep. Two details make it fast. A base whose cell is already crossed out is skipped, because its multiples were erased by the smaller prime that crossed it out. And each sweep starts at i * i, not 2 * i, because every smaller multiple of i carries a factor below i and is already gone. Once i * i passes n there is nothing left to erase, since a surviving composite would need two factors larger than the square root and their product would overshoot n.
Erase multiples instead of testing divisibility
step 1 / 16
Every number from 2 to 16 starts out assumed prime. Testing each one by dividing it costs a fresh scan per number; instead each prime we confirm will erase all of its own multiples in one sweep, so no number is ever tested — only crossed out.
1FUNCTION sieve(n):2 isPrime[2..n] <- TRUE3 i <- 24 WHILE i * i <= n:5 IF isPrime[i] = TRUE:6 FOR j <- i * i TO n STEP i:7 isPrime[j] <- FALSE8 i <- i + 19 FOR k <- 2 TO n:10 IF isPrime[k] = TRUE:11 APPEND k TO primes12 RETURN primes
← / → step · space play · Home restart
Every step in words
Show all 16 steps
- Every number from 2 to 16 starts out assumed prime. Testing each one by dividing it costs a fresh scan per number; instead each prime we confirm will erase all of its own multiples in one sweep, so no number is ever tested — only crossed out.
- 2 survived every earlier sweep, so nothing smaller divides it — 2 is prime, and it now becomes the base whose multiples get erased.
- Cross out 4 = 2 * 2: it has 2 as a factor, so it cannot be prime. The sweep begins at 2 * 2, which for the very first base 2 is also its first multiple 4 — nothing has been skipped over.
- Cross out 6 = 2 * 3: it has 2 as a factor, so it cannot be prime. This costs one write, not a divisibility test.
- Cross out 8 = 2 * 4: it has 2 as a factor, so it cannot be prime. This costs one write, not a divisibility test.
- Cross out 10 = 2 * 5: it has 2 as a factor, so it cannot be prime. This costs one write, not a divisibility test.
- Cross out 12 = 2 * 6: it has 2 as a factor, so it cannot be prime. This costs one write, not a divisibility test.
- Cross out 14 = 2 * 7: it has 2 as a factor, so it cannot be prime. This costs one write, not a divisibility test.
- Cross out 16 = 2 * 8: it has 2 as a factor, so it cannot be prime. This costs one write, not a divisibility test.
- 3 survived every earlier sweep, so nothing smaller divides it — 3 is prime, and it now becomes the base whose multiples get erased.
- Cross out 9. The sweep starts at 3 * 3 = 9 rather than at 2 * 3 = 6, because every multiple of 3 below 9 also carries a factor smaller than 3 and was already erased by that smaller prime.
- 12 = 3 * 4 is on 3's list too, but it was already crossed out by an earlier base — the sieve overwrites it rather than checking first, since one blind write is cheaper than a test.
- Cross out 15 = 3 * 5: it has 3 as a factor, so it cannot be prime. This costs one write, not a divisibility test.
- 4 is already crossed out, so it is composite: 2 divides it. That means every multiple of 4 is also a multiple of 2 and was erased back when 2 swept. Sieving from 4 would only repeat that work, so skip it.
- The loop stops at 5 because 5 * 5 = 25 is already past 16. Any composite left on the board would need two factors both above 4, and their product would exceed 16 — so nothing composite can still be uncrossed.
- Whatever is still uncrossed was never a multiple of anything smaller, so the 6 survivors [2,3,5,7,11,13] are exactly the primes up to 16 — found by erasing, without a single divisibility test.
Now solve it yourself
Watching is the first half. The second is writing it without the animation.