Sieve of Eratosthenes
An ancient algorithm that finds every prime up to N by repeatedly striking out the multiples of each prime in turn.
Contents
Sieve of Eratosthenes
The Sieve of Eratosthenes is a method, more than two thousand years old, for finding all the primes up to some limit N — not by testing each number, but by elimination. Write down the integers from 2 to N. Circle the first, 2: it is prime. Now cross out every larger multiple of 2. Move to the next surviving number, 3: it is prime, so cross out its multiples. Repeat. Whatever is never crossed out is exactly the set of primes.
It is named for Eratosthenes of Cyrene, the polymath who also measured the circumference of the Earth. The sieve's charm is that it never performs a single division: primality falls out of pure marking.
Watch it run
Below, the integers 2 \dots N are laid in a row. A scanning bar selects each new prime, then sweeps across striking out its multiples. The work shrinks pass by pass — by the time the current prime p satisfies p^2 > N, every composite is already gone.
Why it is fast
The sieve's genius is in not repeating work. Two optimizations make it efficient.
- Start at p^2. When you reach prime p, every multiple 2p, 3p, \dots, (p-1)p was already struck by a smaller prime factor. So the first new multiple to cross out is p^2.
- Stop at \sqrt{N}. Once p^2 > N, any remaining composite would need a prime factor larger than \sqrt N paired with one smaller — but the smaller factor already eliminated it. Everything left is prime.
Counting the operations gives a running time of about N \ln\ln N — almost linear in N. The doubly-logarithmic factor grows so slowly it is nearly a constant.