Code for finding the 1000th prime
in [Python]
|
Prev: ANN: PyGUI 2.1
Next: SCGIServer and unusal termination
From: Chris Rebert on 17 Nov 2009 13:21 On Tue, Nov 17, 2009 at 9:27 AM, Diez B. Roggisch <deets(a)nospam.web.de> wrote: > Stefan Behnel wrote: >> Robert P. J. Day, 15.11.2009 15:44: >> Now, all that's left to do is write a prime number generator (a random >> number generator will do, too, but writing a good one isn't easy), run it >> repeatedly in a loop, and check if the returned number is 7919. Once it >> compares equal, you can print the result and you're done. > > That reminds me of the only algorithm I really invented myself: debil sort. There's prior art for this algorithm: http://en.wikipedia.org/wiki/Bogosort > It goes like this: > > L = <list of comparable items> > > while not sorted(L): > Â p = generate_random_permutation(len(L)) > Â L = apply_permutation(L, p) > > print L > > > Great algorithm. Actually works. And the saddest thing: somebody out there > certainly has written something like that by accident... I've spotted > sorting in O(n^3) (with non-deterministic exceptional termination > conditions) already in the wild. Cheers, Chris -- http://blog.rebertia.com
From: Terry Reedy on 17 Nov 2009 15:29
>> 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 |