Difference between revisions of "Sieve of Eratosthenes"
Jump to navigation
Jump to search
(New page: 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 [[Eratosth...) |
|||
| Line 9: | Line 9: | ||
# the unstriked numbers are all the [[prime]]s on the original list. | # the unstriked numbers are all the [[prime]]s on the original list. | ||
[[category:mathematics]] | [[category:mathematics]] | ||
| + | [[Category:Prime Numbers]] | ||
Revision as of 01:23, November 16, 2008
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 unstriked 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 primes on the original list.