Code for finding the 1000th prime

[Peter Otten]

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