Code for finding the 1000th prime
Peter Otten
__peter__ at web.de
Tue Nov 17 17:27:36 CET 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
More information about the Python-list
mailing list