## 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