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:
Given an upper bound value
- Create a list named
prime
of booleans, all set toTrue
, for allnumbers between 0 and the upper bound.
Set prime[0] and prime[1] to
False
Let
p
Loop over all values between 2 and the upper bound (inclusive)
while not prime[p] and 2 <= p <= upper bound:
set p = p + 1
P is now a prime number
set k = p + p
while k <= upper bound
prime[k] = false
k = k + p
The
prime
list now has aTrue
value for those numbers that are prime.
- 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.