Sieve of Eratosthenes

Summary

The sieve of Eratosthenes is an algorithm that finds all the prime numbers up to a given bound $N$. It writes the integers from $2$ to $N$. It takes the smallest number that is not crossed out, which is a prime $p$, and crosses out the multiples $p^2, p^2 + p, p^2 + 2p, \dots$ up to $N$. It repeats this step while $p^2 \le N$. The numbers that are not crossed out at the end are the primes up to $N$.

Remarks

It is enough to start at $p^2$, because a smaller multiple of $p$ has a smaller prime factor, and an earlier step crossed it out. The algorithm needs about $N \log \log N$ operations. The idea of the sieve is the basis of sieve methods in analytic number theory.

Explanations

L1 human

For $N = 30$, cross out the multiples of $2$ from $4$, then the multiples of $3$ from $9$, then the multiples of $5$ from $25$. Then $7^2 = 49 > 30$, so you stop. The numbers left are $2, 3, 5, 7, 11, 13, 17, 19, 23, 29$.