# 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 to`True`

, 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 a`True`

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.