Sieve of Eratosthenes

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search
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 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.