Code for finding the 1000th prime

[Terry Reedy]

>> On Sun, 15 Nov 2009, mrholtsr wrote:
>>
>>> I am absolutely new to python and barely past beginner in programming.
>>> Also I am not a mathematician. Can some one give me pointers for
>>> finding the 1000th. prime for a course I am taking over the internet
>>> on Introduction to Computer Science and Programming. Thanks, Ray

Now for a serious answer ;-)

The intent of the problem is that you write a function prime_n(n) that 
returns the nth prime, where 2 is the first. This is different from 
prime(n), which would return True/False depending on whether n is a 
prime or not. Then you are to execute prime_n(1000) and submit that.

The person who set the problem expects that you will have learned and 
still remember the definition of prime numbers and a few basic facts 
about them. Or that you will look these up on a site such as Wikipedia. 
Since you are not taking a math course, you should expect that the basic 
facts will be enough.

For this problem, the relevant fact is that there is no formula that 
will directly compute the nth prime from n. Instead, one must generate 
the first, the second, the third, ...., until reaching the nth. The 
easiest and direct way to do this is to use primes 1 to i to test 
whether counts greater than prime i are primes, until you find the 
(i+1)th prime.

You may find references to the Sieve of Eratosthenes. It generates all 
the primes up to a certain number N by testing prime divisors in a 
different order. But to use it find the nth, one has to guess that some 
N will be larger than the nth, run the Sieve, and see whether you got 
the nth or have to try a larger value of N. For the 1000th, it turns out 
that N=10000 works. In general picking an N such that N * log(N) is 
'comfortably' larger than n will work. But this guessing is not actually 
necessary in Python which has *expandable* arrays.

A different approach, at least as difficult, is to write a program that 
looks up the answer by accessing a public database of primes.
http://en.wikipedia.org/wiki/List_of_primes
lists some of these in its External Links section.

Terry Jan Reedy