Sieve of Eratosthenes

Revision as of 10:51, 27 June 2006 by Fedja (talk | contribs) (Description of the algorithm)

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 $2$ 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!


An image is supposed to go here. You can help us out by creating one and editing it in. Thanks.


Related Links

See also

Invalid username
Login to AoPS