Difference between revisions of "Sieve of Eratosthenes"
Jump to navigation
Jump to search
m (cat) |
|||
| Line 1: | Line 1: | ||
| − | The '''Sieve of Eratosthenes''' is a simple [[algorithm]] for identifying all prime | + | The '''Sieve of Eratosthenes''' is a simple [[algorithm]] for identifying all [[prime number]]s up to a certain integer. It was discovered by the ancient [[Greek]] [[mathematician]] [[Eratosthenes]]. |
The [[algorithm]] is as follows: | The [[algorithm]] is as follows: | ||
| Line 8: | Line 8: | ||
# Continue this process until all multiples have been checked for primality. | # Continue this process until all multiples have been checked for primality. | ||
# 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: | + | [[Category:Number Theory]] |
Revision as of 11:37, 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.