Last modified on December 2, 2009, at 01:48

Sieve of Eratosthenes

The Sieve of Eratosthenes is a simple algorithm for identifying all prime numbers up to a certain integer. It was discovered by the ancient Greek mathematician Eratosthenes.

The algorithm is as follows:

  1. List sequentially all the integers to be checked up to and including the maximum integer, such as "2, 3, 4, 5, 6, ..." (By definition, the number 1 is not prime).
  2. Take the first number (e.g., "2"), and strike from the list all of its multiples (e.g., "4, 6, 8, 10, ...").
  3. Take the second unstricken number (e.g., "3"), and likewise strike from the list all of its multiples (e.g., "6, 9, 12, 15, ...").
  4. Continue this process until all multiples have been checked for primality.
  5. The unstricken numbers are all the primes on the original list.