A Concise Introduction to Programming in Python

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 b e

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