Enumeration to find Nth prime with Python

Question

I have decided it is about time that i should start learning to code. I have some knowledge of HTML and CSS but i want to be able to develop for iOS. I am aware i have a long way to go, but i aim to get there step by step.

I'm working through the MIT Python course on iTunes U and I am stuck on the homework. I understand the concept of enumeration and testing every possible outcome to find the primes, however what i have tried so far has failed me. My closest attempt is the following.

# counting confirmed primes. For loop should do remainder tests on
# all testNumbers, unless caught by the if statements that rule out
# multiples of 2,3,5,7 to speed things up. divisor increments by one
# on those numbers that do not get pulled by qualifying if statements

testNumber = 2
confirmedPrime = 0

while (confirmedPrime < 1001):
        for divisor in range(1, testNumber+1):
                if (testNumber/2)*2== testNumber:
                        testNumber += 1
                elif (testNumber/3)*3 == testNumber:
                        testNumber += 1
                elif (testNumber/5)*5 == testNumber:
                        testNumber += 1
                elif (testNumber/7)*7 == testNumber:
                        testNumber += 1
                elif(testNumber%divisor == 0):
                        testNumber += 1
        confirmedPrime +=1
print testNumber

This however doesn't return the "7919" i am expecting but. It returns "7507" So somewhere there are some composites slipping through the net.

I have hunted through this site and not managed to solve it so I thought I would ask.

Answer 1

A few bits are off here, so let's go step by step.

You start by setting initial values, which is perfectly reasonable.

testNumber=2
confirmedPrime = 0

Then you go into a while loop, continuing until the value of the variable confirmedPrime is has reached (i.e. is equal to or bigger than) 1001. I suppose your task is to find the 1000th prime, but doing it like this you're actually finding the 1001st, because the while loop continues until confirmedPrime has the value of 1001. Change it to

while(confirmedPrime < 1000):

You immediately go into another loop, and here comes the first problem, even though it isn't what's giving you the wrong answer.

    for divisor in range(1, testNumber+1)
        if (testNumber/2)*2 == testNumber:
            ...

Doing the tests for multipliers of 2, 3, 5 and 7 inside the for loop doesn't make any sense, as you only have to to this once for each value of testNumber. So that part of the testing should be moved out of the for loop.

    if (testNumber/2)*2 = testNumber: # Why not use modulo here too for consistency?
        testNumber += 1
    elif ...
        ...
    else:
        for divisor in range(...):

The next part is testing for other, larger divisors. You are testing divisors in the range 1 to testNumber+1. I'm not sure why you're doing this, but it's not a good idea, as your modulo test will always return zero when you come to the second last iteration, testing testNumber%testNumber. So you should change it to testNumber-1, in fact you can stop when you have reached the square root of testNumber, but I'll leave it to you to figure out why.

Now comes the biggest problem: After the for loop is finished, you increment confirmedPrimes by 1 without actually checking if you found a prime or not. So, incrementing confirmedPrimes should only happen if none of the first tests were true and none of the "divisor tests" turned out to be true.

Rewritten using underscores instead of mixedCase (which is bad python mojo), consistent spacing etc:

import math

test_number = 7       # Already know up to 7
confirmed_primes = 4  # Already know about 2, 3, 5 and 7

while confirmed_primes < 1000:
    test_number += 1

    if test_number % 2 and test_number % 3 and test_number % 5 and test_number % 7:
        is_prime = True

        for divisor in range(11, int(math.sqrt(test_number))+1):
            if test_number % divisor == 0:
                is_prime = False

        if is_prime:
            confirmed_primes += 1

print test_number

Answer 2

I don't understand exactly how your algorithm is supposed to find a prime number.

A number is said to be prime if it's only divisible by 1 or himself.

Another definition is that a number is said to be prime if it's not divisible by any prime number smaller than it.

This can be the base of your algorithm, speeding up the process by a lot.

def nth_prime(n):
    prime_list = []
    current = 2
    count = 0
    while(count < n):
        is_prime = True
        for prime in prime_list:
            if current % prime == 0:
                is_prime = False
                break
        if is_prime:
            prime_list.append(current)
            count += 1
        current += 1
    return current - 1

print nth_prime(1000) # => 7919