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.

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