Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Python > Code for finding the 1000th prime

Reply
Thread Tools

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
 
Reply With Quote
 
 
 
 
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
Twitter: http://twitter.com/rpjday
================================================== ======================
 
Reply With Quote
 
 
 
 
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
 
Reply With Quote
 
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.
 
Reply With Quote
 
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"



 
Reply With Quote
 
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
 
Reply With Quote
 
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

 
Reply With Quote
 
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.
 
Reply With Quote
 
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

 
Reply With Quote
 
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
conditions) already in the wild.

Diez
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Re: Program to compute and print 1000th prime number Robert P. J. Day Python 5 01-17-2011 10:02 PM
Solutions for finding the 1000th prime Neal Python 2 05-21-2010 06:12 PM
Re: [Tutor] Finding prime numbers Shawn Milochik Python 4 09-20-2007 03:44 PM
Prime numbers: addative property modulo p, where p is prime Jeremy Fischer Perl Misc 0 01-16-2005 05:53 PM
1000th pings a day df Computer Security 3 10-15-2003 05:09 AM



Advertisments