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$.