..  _cosc1336-lab8:

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)
    
        a. while not prime[p] and 2 <= p <= upper bound:
            
            1. set p = p + 1

        b. P is now a prime number
    
        c. set k = p + p
    
        d. while k <= upper bound
        
            1. prime[k] = false
        
            2. k = k + p

    5. The ``prime`` list now has a ``True`` value for those numbers that are prime.
    
        a. 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:

..  code-block:: text

    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:

..  code-block:: text

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

..  vim:filetype=rst spell: