Code for finding the 1000th prime

[Diez B. Roggisch]

Stefan Behnel wrote:

> Robert P. J. Day, 15.11.2009 15:44:
>> 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
>> 
>>   it's 7919.
> 
> 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.


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.

Diez