The Sieve of Eratosthenes: Finding Primes the Smart Way

The Sieve of Eratosthenes finds every prime up to a limit by repeatedly crossing out the multiples of each prime you find. Whatever survives is prime.

It's elegant, ancient and still one of the fastest ways to generate a list of primes.

How the sieve works

1. Write the numbers 2 to N.
2. Circle 2 (prime) and cross out every multiple of 2.
3. Move to the next un-crossed number (3), circle it, cross out its multiples.
4. Repeat. Everything still circled is prime.

A small example up to 30

The survivors are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 — the ten primes below 30. You only need to sieve multiples up to √N.

Why it's efficient

Each composite is crossed out by its prime factors rather than tested individually. This makes the sieve far faster than checking each number for primality when you want all primes in a range.

Sieve vs trial division

Use the sieve to generate many primes at once; use trial division (as in the Prime Number Checker) to test a single number.