Lab 8: Sieve of Eratosthenes

OK, I know some of you think math is something to be avoided. I was with you, until I figured out how cool math can really be. In the end I taught myself a lot of math, things I ignored in school. Even today, I regret not knowing more!

Let’s use a classic math scheme to explore an interesting concept in math: the Prime Numbers.

Here is our problem:

Find all prime numbers between two and some upper value. I will show you the algorithm using pseudo code, your job is to code this up using Python. To make it a bit more interesting, you need two files for this:

  • A driver program that asks the user for the upper bound to use in generating the prime numbers,
  • A second file that contains the single function named prime. This function returns a list as described below.

What is a prime number?

Just in case you do not remember the definition of a prime number, here it is:

A prime number is any number greater than 1 that can be divided evenly only by 1 and itself.

The Sieve of Eratosthenes is a clever scheme that generates a table of all numbers, then crosses off all numbers that are multiples of other numbers. What is left are the prime numbers.

The algorithm

Here is the algorithm, in pseudo-code:

  1. Given an upper bound value

  2. Create a list named prime of booleans, all set to True, for all

    numbers between 0 and the upper bound.

  3. Set prime[0] and prime[1] to False

  4. Let p Loop over all values between 2 and the upper bound (inclusive)

    1. while not prime[p] and 2 <= p <= upper bound:

      1. set p = p + 1
    2. P is now a prime number

    3. set k = p + p

    4. while k <= upper bound

      1. prime[k] = false
      2. k = k + p
  1. The prime list now has a True value for those numbers that are prime.

    1. Generate the result list with a loop, adding numbers to the list
      where prime[p] == True.

Note

This pseudo-code is hard to follow on your first pass through it. It does help to run through an example (see below) and watch it at work. After reading the logic a few times, and studying the example output, you should see how it works.

Here is another explanation of how this works.

We start on a prime number (2) loop over all numbers from 2 to the upper bound looking for a prime number (one whose value in the prime list is True. We will discover that 2 is prime and stop there. Next we set up a new variable, k and initialize it to the sum of the current prime number with itself (that is a multiple of this prime number. The resulting number is not prime. We continue adding the current prime number to k until we exceed the upper bound. In effect, this removes known non-prime numbers from the list. Returning to the outer loop, we will step up to the next number to consider, skipping anything that is known to be non-prime. We stop on the next prime number and continue eliminating multiples of that new number. When we finish the outer loop, the prime list has a value of True for any number that is prime. We can scan this list (in another loop) and generate a final list of all prime numbers between 0 and the upper bound.

Work through this scheme manually for an upper bound of 10. You should end up with prime numbers [2,3,5,7]

Write the code in stages, and add print statements to watch what is going on, it will help!

I did exactly that to build this sample output showing the process as the routine generates the results for an upper bound of 10:

Enter the upper bound for the prime number generator:10
generating all primes between 2 and 10
checking 2
    2 is prime
    4 is not prime
    6 is not prime
    8 is not prime
    10 is not prime
checking 3
    3 is prime
    6 is not prime
    9 is not prime
checking 4
    5 is prime
    10 is not prime
checking 5
    5 is prime
    10 is not prime
checking 6
    7 is prime
checking 7
    7 is prime
checking 8
checking 9
checking 10
Prime numbers are [2, 3, 5, 7]

Here is the solution for an upper bound of 250:

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53,
59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113,
127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181,
191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241]

Your final code should be tested for this example before you turn it in.