Question

I am trying to wrap my head around the prime number generation for the 1000th number. I know that any prime can be made using other primes, but in writing code how do I disqualify candidates and how would I solve it with both a brute force method and a method with some kind of cost? Like in Lecture 3 or 4. Is their a good book of programming projects that might help fill in the gaps of the problem sets. what gaps am I leaving out? Also Which inspiration is more interesting Fermat or Messier?

Answer 1

Hi, I think you're searching too complicated things. The most basic method is the trial division method:
To know if a number p is a prime is to divide it by all the number from 2 to p-1. If the rest of integer division of p by q is 0 (p % q == 0), then q is a factor of p and p is not a prime number. It is the method described in pset1a.pdf.
Now you could refine a little bit this method by noting the following: since multiiplication is a commutative operation (a * b = b * a), you only have to test the dividers until \[\sqrt{p}\] This will accelerate the program. There are a lot of much more complicated and efficient algorithms, but I don't think that's the point of this exercise. Here are two useful references if you want more informations:
http://en.wikipedia.org/wiki/Prime_number
http://www.troubleshooters.com/codecorn/primenumbers/primenumbers.htm

Hope this helps ! Let me know !

Answer 2

there are readings associated with the lectures.
the tutorial in the Python documentation is a must - it should have been installed on your computer. http://docs.python.org/

Answer 3

http://docs.python.org/tutorial/controlflow.html