Velocity Reviews > Code for finding the 1000th prime

# Code for finding the 1000th prime

mrholtsr
Guest
Posts: n/a

 11-15-2009
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

Robert P. J. Day
Guest
Posts: n/a

 11-15-2009
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.

rday
--

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

Linux Consulting, Training and Kernel Pedantry.

Web page: http://crashcourse.ca
================================================== ======================

Diez B. Roggisch
Guest
Posts: n/a

 11-15-2009
mrholtsr schrieb:
> 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

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

Diez

mrholtsr
Guest
Posts: n/a

 11-16-2009
On Nov 15, 10:02*am, "Diez B. Roggisch" <(E-Mail Removed)> wrote:
> mrholtsr schrieb:
>
> > 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

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

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

sturlamolden
Guest
Posts: n/a

 11-16-2009
On 15 Nov, 15:30, mrholtsr <(E-Mail Removed)> 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

print "7919"

Stefan Behnel
Guest
Posts: n/a

 11-17-2009
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
Guest
Posts: n/a

 11-17-2009
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.

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
Guest
Posts: n/a

 11-17-2009
2009/11/15 mrholtsr <(E-Mail Removed)>:
> 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
> --
> 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
Guest
Posts: n/a

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

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
Guest
Posts: n/a

 11-17-2009
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

Diez