Project 2 Primes

Todays Topic:  How to do project 2.

So the current project due in CS 373 is Primes.  It has to deal with how to compute a number from 4 prime numbers by adding them all together.  As discussed in class there are some pretty good ways to do this.  If you took CS 315 with Downing then you might have had to do this problem in java.  The only difference is that now we're not being timed, it has to be used in python and use subversion.  The best way is to start out with a list of prime numbers.

There is a few different ways to get a list of prime numbers.  You could google it  (link: http://tinyurl.com/deehyp) and copy paste that into emacs (or your choice of text editor) then set it up as an array called primes and manually insert commas and remove whitespaces and newlines (\n).  There is another way and that involves computing the primes yourself.  I chose this method since we would need all of the prime numbers slightly past 2500000 since the max number N is 10000000 and can be made up of 4 different numbers.   

Another way to get the primes is to write a loop that will take a number and try to divide it by all numbers that are smaller than it to n/2.  If it can't be divided wholey with integers then it must be prime and then add it to the list.  [Use 2 nested loops to accomplish this]   The other better/faster way is to do the Sieve of Eratosthenes.  (I actually did this in High School yay for me?).  Also wikipedia

Now that you have gotten a list of primes in python (hopefully) the easiest way to get them all out is to do this:  "print primes"   [where primes is you list of primes].  Then just copy all of that printed out stuff and make a global array and paste it in.

To compute the primes Downing suggested this idea.  If the number is even then pick two of the primes are to be even.  If it is odd then pick an odd and then an even prime.  Of course the only even prime out there is 2.

I suggest 4 nest for loops and use the idea above to set the two outer loops to start at those numbers (2 and 2 if even, 2 and 3 if odd). Then just run through the for loops grabbing prime numbers from the list of primes.  You should create a boolean flag for when you find the numbers to easily break out of the loops.  Then print them out. 

However there are exceptions to the summation of 4 primes being the desired number.  If the number is ≤ 7 then the program should print "Impossible.".  Also there might be a few numbers that are not able to compute from a list of prime numbers and should also print "Impossible.".

A few suggestions:

Get a list of all the primes up to 10000000.  It really can't hurt.

Make a big list of unit tests and use high numbers.

Find your list of primes and then submit to subversion.

Ask questions if you need help.

Next week's topic: Unit testing and why it's not annoying.