Chapter 14

# Lists

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) ...`

Get A Concise Introduction to Programming in Python now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.