Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

Code for finding the 1000th prime

593 views
Skip to first unread message

mrholtsr

unread,
Nov 15, 2009, 9:30:50 AM11/15/09
to
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

Diez B. Roggisch

unread,
Nov 15, 2009, 10:02:09 AM11/15/09
to
mrholtsr schrieb:

Do you really think we are so retarded that we don't remember you posted
the same question a week ago?

Diez

Robert P. J. Day

unread,
Nov 15, 2009, 9:44:43 AM11/15/09
to mrholtsr, pytho...@python.org

it's 7919.

rday
--

========================================================================
Robert P. J. Day Waterloo, Ontario, CANADA

Linux Consulting, Training and Kernel Pedantry.

Web page: http://crashcourse.ca
Twitter: http://twitter.com/rpjday
========================================================================

mrholtsr

unread,
Nov 16, 2009, 9:00:18 AM11/16/09
to

Mea Culpa. I didn't realize at the time that this group was the same
as the newsletter. Won't do it again.

sturlamolden

unread,
Nov 16, 2009, 9:06:55 AM11/16/09
to


print "7919"

Stefan Behnel

unread,
Nov 17, 2009, 8:00:35 AM11/17/09
to
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.

Stefan

Carsten Haese

unread,
Nov 17, 2009, 9:33:34 AM11/17/09
to pytho...@python.org

Just do a brute-force search:

for i in range(10000):
if i==7919:
# Found it!
print i

;-)

--
Carsten Haese
http://informixdb.sourceforge.net

Himanshu

unread,
Nov 17, 2009, 10:41:09 AM11/17/09
to mrholtsr, pytho...@python.org
2009/11/15 mrholtsr <mrho...@gmail.com>:
> --
> http://mail.python.org/mailman/listinfo/python-list
>

Consider skipping such "mathematically oriented" exercises in an
introductory course on python if targeted to a general audience.

Peter Otten

unread,
Nov 17, 2009, 11:27:36 AM11/17/09
to
mrholtsr wrote:

When you encounter a problem that you find hard try to split it into simpler
subproblems. Example:

To find the 1000th prime start with a program that finds all integers

i = 1
while True:
print i
i = i + 1

If you run that it will print integers until you hit Ctrl-C. Python offers
an elegant construct that helps you encapsulate the logic of a loop, called
"generator". With that we can rewrite the all-integers program as

def all_natural_numbers():
i = 1
while True:
yield i
i = i + 1

for i in all_natural_numbers():
print i

Now let's tackle the next step: we want only prime numbers, but don't know
how to check for them. How can we postpone that problem and still continue
with our program? Easy: introduce a function where the check will ultimately
go but have it do something that we do understand right now:

def isprime(candidate):
return candidate != 42

Why not check for candidate == 42? We would only ever get one "pseudo-
prime", but we need at least 1000 of them. With the above bold assumption
the program becomes

def isprime(candidate):
return candidate != 42

def all_natural_numbers():
i = 1
while True:
yield i
i = i + 1

for i in all_natural_numbers():
if isprime(i):
print i

While the actual output is a bit unorthodox we now have the structure to
print all prime numbers. Again we can wrap the logic into a generator:

def isprime(candidate):
return candidate != 42

def all_natural_numbers():
i = 1
while True:
yield i
i = i + 1

def all_prime_numbers():
for i in all_natural_numbers():
if isprime(i):
yield i

for p in all_prime_numbers():
print p

We are actually only interested in the 1000th prime. We can find that by
counting over all prime numbers:

i = 1
for p in all_prime_numbers():
if i == 1000:
print p
break
i = i + 1

We can wrap this step in a function for future reuse:

# all_natural_numbers(), all_prime_numbers(),
# and isprime() as before

def nth_item(items, n):
i = 1
for item in items:
if i == n:
return item
i = i + 1
# raise Exception("here be dragons")

print nth_item(all_prime_numbers(), 1000)

OK, we now have a nice clean python script that tells us that the 1000th
prime number is 1001, a finding that will meet some opposition among
mathematicians. Let's turn to wikipedia for help:

"""
a prime number (or a prime) is a natural number which has exactly two
distinct natural number divisors: 1 and itself.
...
The number 1 is by definition not a prime number.
"""

Translated into Python:

def isprime(candidate):
if candidate == 1:
return False # 1 is not a prime
for potential_divisor in range(2, candidate):
if int(candidate/potential_divisor)*potential_divisor == candidate:
# candidate could be divided by potential divisor
# without rest, so it's not a prime
return False
# we didn't find a divisor for candidate
# -- it must be a prime
return True

Now while this test for primality is not the most beautiful code I've ever
written it should give you the correct result. As a first step to improve it
have a look at the % ("modulo") operator in your textbook. Then try to
reduce the number of potential divisors.

Peter

Diez B. Roggisch

unread,
Nov 17, 2009, 12:27:49 PM11/17/09
to
Stefan Behnel wrote:

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

Chris Rebert

unread,
Nov 17, 2009, 1:21:15 PM11/17/09
to Diez B. Roggisch, pytho...@python.org
On Tue, Nov 17, 2009 at 9:27 AM, Diez B. Roggisch <de...@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

Edward A. Falk

unread,
Nov 17, 2009, 2:48:46 PM11/17/09
to

Terry Reedy

unread,
Nov 17, 2009, 3:29:47 PM11/17/09
to pytho...@python.org

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

0 new messages