Enumerating Primes

- [Initialize] Let be the list of all odd integers between and . Let be the list of primes found so far.
- [Finished?] Let be the first element of . If , append each element of to and terminate. Otherwise append to .
- [Cross Off] Set equal to the sublist of elements in that are not divisible by . Go to step 2.

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

sage: eratosthenes(50) [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

William 2007-06-01