The sieve of Eratosthenes

How does one list all the prime numbers up to a given number $N$? Eratosthenes of Cyrene (3rd century BC, librarian of Alexandria) invented an elegant algorithm: the sieve (in Greek koskinon, “sieve”), which is still today the simplest method for generating tables of prime numbers.

Example — Sieve of Eratosthenes up to 30

One writes the numbers from $2$ to $30$ and proceeds as follows:

1. Circle the first uncrossed number ($2$): it is prime.
2. Cross out all its subsequent multiples ($4,6,8,\ldots,30$).
3. Go back to step 1 on the next uncrossed number ($3$), then $5$, then $7$.
4. When you reach a prime $p$ with $p^2>N$ (here $p=7$, since $7^2=49>30$) you may stop: all the remaining uncrossed numbers are prime.

There remain: $\boxed{2,3,5,7,11,13,17,19,23,29}$ — the $10$ primes up to $30$.

The sieve up to 30: circled in red the primes, in grey the numbers crossed out because composite.

Links

Topics: Numbers and operations
Concepts: Sieve of Eratosthenes · Prime number
Methods: Sieve of Eratosthenes
Skills: Calculate
People: Eratosthenes