Sieve of Eratosthenes
From Conservapedia
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:
- 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).
- Take the first number (e.g., "2"), and strike from the list all of its multiples (e.g., "4, 6, 8, 10, ...").
- Take the second unstricken number (e.g., "3"), and likewise strike from the list all of its multiples (e.g., "6, 9, 12, 15, ...").
- Continue this process until all multiples have been checked for primality.
- The unstricken numbers are all the primes on the original list.