Sieve of Eratosthenes

From Conservapedia
This is the current revision of Sieve of Eratosthenes as edited by DanielPulido (Talk | contribs) at 01:48, December 2, 2009. This URL is a permanent link to this version of this page.

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

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.