# 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

```