sieve of Eratosthenes
Let , which is of course known to be prime. Mark all positive multiples of (e.g. ), up until , as composite. Now let be the smallest number not marked as composite (in this case, ); it must be the next prime. Again, mark all positive multiples of as composite. Continue this process while . When done, all numbers less than that have not been marked as composite are prime.
For many years, the sieve of Eratosthenes was the fastest known algorithm for listing primes. Today, there are faster methods, such as a quadratic sieve.
|Title||sieve of Eratosthenes|
|Date of creation||2013-03-22 12:39:34|
|Last modified on||2013-03-22 12:39:34|
|Last modified by||mathcam (2727)|