Difference between revisions of "Sieve of Eratosthenes"

Latest revision as of 01:48, December 2, 2009

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.

@@ Line 5: / Line 5: @@
 # 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 unstriked number (e.g., "3"), and likewise strike from the list all of its multiples (e.g., "6, 9, 12, 15, ...").
+# 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 unstriked numbers are all the [[prime]]s on the original list.
+# The unstricken numbers are all the [[prime]]s on the original list.
 [[Category:Number Theory]]