Animation of the Sieve of Eratosthenes up to 120 (with the optimization of starting from squares).

The Sieve of Eratosthenes is a simple way to find all the prime numbers up to some number n:

1. Write all the numbers from 2 up to n onto a piece of paper, in order. We will perform the following steps so that all the non-prime numbers will be crossed out, and what's left will be the primes.
2. Choose the first, i.e. the smallest available number. Call it p (it will be 2 at the start). If there's no more available numbers, stop.
3. Count up from p as 2p, 3p, 4p, ..., up to n in steps of p, and cross out each of those numbers. Some numbers will be already crossed out, that's okay. Do not cross out the number p itself but consider it no longer available.
4. Go back to step 2.

When the algorithm is finished all the numbers that are left not crossed out are all the prime numbers from 2 up to n.

As an optimization we can start the counting in step 3 from p², and stop in step 2 when p² is greater than n.