Sieve of Eratosthenes
From AoPSWiki
| Error creating thumbnail: sh: /usr/bin/convert: No such file or directory |
The Sieve of Eratosthenes is a simple method to quickly uncover a short list of prime numbers.
Description of the algorithm
Begin by writing the positive integers starting with 
up to the maximal number you are interested in. Now, during each step, take the first number that is neither crossed out 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!
Below is an example of how to use this sieve to find the primes up to
. Note that after just two steps, no new crossouts appear. In general, one can forget about crossouts and start just circling all remaining numbers once a number exceeding the square root of the maximal number we are interested in is circled (in our example it is 
). The reason is that if a number 
is composite, then it has a prime divisor not exceeding 
.
