Code for finding the 1000th prime

[Chris Rebert]

On Tue, Nov 17, 2009 at 9:27 AM, Diez B. Roggisch <deets at 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