Sieve of Eratosthenes
The Sieve of Eratosthenes is a simple way to find all the prime numbers up to some number n:
- 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.
- 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.
- 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.
- 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 p2, and stop in step 2 when p2 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.
Sieve Of Eratosthenes Media
Sieve of Eratosthenes: algorithm steps for primes below 121 (including optimization of starting from prime's square).
