O'Reilly logo

A Concise Introduction to Programming in Python by Mark J. Johnson

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required