## Enumerating Primes

The Sieve of Eratosthenes is an efficient way to enumerate all primes up to  . The sieve works by first writing down all numbers up to , noting that  is prime, and crossing off all multiples of  . Next, note that the first number not crossed off is  , which is prime, and cross off all multiples of  , etc. Repeating this process, we obtain a list of the primes up to  . Formally, the algorithm is as follows:

Algorithm 1.2 (Sieve of Eratosthenes)   Given a positive integer , this algorithm computes a list of the primes up to .
1. [Initialize] Let be the list of all odd integers between and . Let be the list of primes found so far.
2. [Finished?] Let be the first element of . If , append each element of  to  and terminate. Otherwise append to .
3. [Cross Off] Set  equal to the sublist of elements in  that are not divisible by  . Go to step 2.

For example, to list the primes using the sieve, we proceed as follows. First and

We append to and cross off all multiples of to obtain the new list

Next we append to , obtaining , and cross off the multiples of , to obtain Because , we append to and find that the primes less than are

Proof. [Proof of Algorithm 1.2.3] The part of the algorithm that is not clear is that when the first element of satisfies , then each element of is prime. To see this, suppose is in , so and that  is divisible by no prime that is . Write with the distinct primes ordered so that . If for each  and there is more than one  , then , a contradiction. Thus some  is less than , which also contradicts our assumptions on  .

SAGE Example 1.2   The eratosthenes command implements the sieve in SAGE:
sage: eratosthenes(50)
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]


William 2007-06-01