Sieve of Eratosthenes - Simple English Wikipedia, the free encyclopedia

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.

This is allowed because for each number k that is smaller than p, the number kp in step 3 will be already crossed out as part of the algorithm working for some previous prime that is smaller than p – the smallest such prime which divides k evenly.

This short article about mathematics can be made longer. You can help Wikipedia by adding to it.