CODEWITHSUNDEEP
pythonprimes
decb24
decb24

Reputation: 21

Finding the nth Prime

I am trying to create an algorithm which will output the nth prime number. I have written up the code but whenever I run it I am given the 980th prime, when it should output the 1000th prime?

testNumber = 1
countPrimes = 0
testCounter = 2
isPrime = False
currentPrime = 0

while(countPrimes <= 1021): #runs for the first 1k primes
    testCounter=2
    isPrime = True
    if(testNumber%2 != 0): #checks if test number is odd
        while(testCounter*testCounter < testNumber): #counter^2 needs to be less than testNumber
            if(testNumber%testCounter == 0):
                isPrime = False
            testCounter = testCounter + 1
        if(isPrime==True):
            countPrimes = countPrimes + 1
            currentPrime = testNumber
    testNumber+=1

print currentPrime

Upvotes: 0

Views: 146

Answers (1)

Brionius
Brionius

Reputation: 14098

The problem is that your code is also counting odd perfect squares (9, 25, 49, etc) as prime numbers. That is because your code stops testing for divisibility just before you get to the square root of the number. To exclude perfect squares, you need to check one more integer:

I.e. instead of:

while(testCounter*testCounter < testNumber): #counter^2 needs to be less than testNumber

try this:

while(testCounter*testCounter < testNumber + 1): #counter^2 needs to be less than testNumber

Additionally, you'll still be one off because your code counts 0 and 1 as prime, and doesn't count 2.

Upvotes: 1

Related Questions