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
--
http://mail.python.org/mailman/listinfo/python-list
