Difference between revisions of "Sieve of Eratosthenes"
m (→See also) |
(added a section title) |
||
| Line 1: | Line 1: | ||
| + | ===Description of the algorithm=== | ||
| + | |||
The Sieve of Eratosthenes is a simple method to quickly uncover a short list of primes. Begin by writing positive numbers starting with <math>2</math> up to the maximal number you are interested in. Now, during each step, take the first number that is neither crossed, nor circled, circle it, and cross all larger numbers divisible by it. Keep doing this until all numbers are either circled or crossed. The circled numbers are the primes! | The Sieve of Eratosthenes is a simple method to quickly uncover a short list of primes. Begin by writing positive numbers starting with <math>2</math> up to the maximal number you are interested in. Now, during each step, take the first number that is neither crossed, nor circled, circle it, and cross all larger numbers divisible by it. Keep doing this until all numbers are either circled or crossed. The circled numbers are the primes! | ||
Revision as of 17:21, 19 June 2006
Description of the algorithm
The Sieve of Eratosthenes is a simple method to quickly uncover a short list of primes. Begin by writing positive numbers starting with 
up to the maximal number you are interested in. Now, during each step, take the first number that is neither crossed, nor circled, circle it, and cross all larger numbers divisible by it. Keep doing this until all numbers are either circled or crossed. The circled numbers are the primes!
