From: Chris Rebert on
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

>> 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

First  |  Prev  | 
Pages: 1 2 3
Prev: ANN: PyGUI 2.1
Next: SCGIServer and unusal termination