Chapter 14

The sieve of Eratosthenes is an algorithm for making a list of primes that dates back to at least the third century BC:

` List the integers, beginning with 2.`

` Circle 2 (it must be prime),`

` and cross out all of its multiples. They cannot be prime.`

` Circle the next integer that is not yet crossed out (3),`

` and cross out its multiples.`

` Repeat.`

Here is a straight-forward implementation that creates a list of the primes. Recall that the output of the range() function is not itself a list but may be converted to one.

Listing 14.1: Sieve of Eratosthenes

` 1 # sieve.py`

2

` 3 def sieve(n):`

` 4 primes = list(range(2, n + 1))`

` 5 for k in range(2, n + 1):`

` 6 if k in primes:`

` 7 for j in range(2 * k, n + 1, k):`

` 8 if j in primes:`

` 9 primes.remove(j) ...`

Start Free Trial

No credit card required