sieve of Eratosthenes

The sieve of Eratosthenes is a simple algorithm for generating a list of the prime numbers between $1$ and some integer $N\ge 2$.

Let $p=2$, which is of course known to be prime. Mark all positive multiples of $p$ (e.g. $2,4,6,8\mathrm{\dots }$), up until $N$, as composite. Now let $p$ be the smallest number not marked as composite (in this case, $3$); it must be the next prime. Again, mark all positive multiples of $p$ as composite. Continue this process while $p\le \sqrt{N}$. When done, all numbers less than $N$ 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
Canonical name	SieveOfEratosthenes
Date of creation	2013-03-22 12:39:34
Last modified on	2013-03-22 12:39:34
Owner	mathcam (2727)
Last modified by	mathcam (2727)
Numerical id	6
Author	mathcam (2727)
Entry type	Definition
Classification	msc 11A41
Related topic	BrunsPureSieve