# Checking for the nth prime number between 1 and 1,000,000, must compute 1,000,000th in under 3 minutes

My mission is as the title states. Here is the original code, before optimizing slightly (but still not enough). Revised code is in my answer, and it still needs work.

Also, I want to write this without having to import any libraries. Time is only there for me to test, of course, time.

Here's the original code, before optimizing:

print("Enter a number n, 1-1,000,000 to find the nth prime number.")
goal=int(input("Number: "))

if goal>1000000:         #closes the program if the number doesn't fit the parameters
exit()
if goal==1:              #takes care of the first prime, which is 2
print("2")
if goal==2:              #and then the second, which is 3
print("3")

chk=5         #the next odd number after 3, which is already taken care of above
primes=2    #the number of primes recorded, after counting 2 and 3.
x=0         #the last recorded prime number
while primes<goal:
if  chk<9:     #if the number is odd and below 9....
primes+=1  #it's prime
x=chk      #record that number
chk+=2     #and check the next odd number

else:              #if it's =>9......
odds=3         #check to see if it's divisible by the smallest odd number
sqrtk=chk**.5  #all the way up to the square root of k

while odds<sqrtk or odds==sqrtk:   #if at any time...
if chk%odds==0:                #...k is divisible by this odd number....
chk+=2                     #then raise the value of k to the next odd number
break
else:            #if not...
odds+=2         #check to see if it's divisible by the next odd number.

if odds>sqrtk:             #if k isn't divisible by any r
primes+=1        #we have a prime number
x=chk         #record that number
chk+=2        #check the next odd number to see if it's prime
odds=3         #and reset r back to 3 to use it next time

if primes==goal:                  #once we've reached the desired amount of prime numbers
print("The",goal,"prime number is:",x)      #print that prime number


Style (and related tools)

As described in Vogel612's answer, many things are wrong concerning the style. You can use pep8 (or its online version) to check it automatically and autopep8 to try to fix this automatically. You'll find various other convenient tools to check your code such as pylint, pyflakes or pychecker.

Separation of concerns and code organisation

You could create a function to look for the prime number and then call it when you want to print the result.

You'd get something like :

def get_nth_prime(goal):
if goal > 1000000:
return None
if goal == 1:  # first prime is 2
return 2
if goal == 2:  # second prime is 3
return 3

chk = 5  # the next odd number after 3, which is already taken care of above
primes = 2  # the number of primes recorded, after counting 2 and 3.
while primes < goal:
if chk < 9:  # if the number is odd and below 9....
primes += 1  # it's prime
chk += 2  # and check the next odd number

else:  # if it's =>9......
odds = 3  # check to see if it's divisible by the smallest odd number
sqrtk = chk ** .5  # all the way up to the square root of chk

while odds < sqrtk or odds == sqrtk:  # if at any time...
if chk % odds == 0:  # ...chk is divisible by this odd number....
chk += 2  # then raise the value of chk to the next odd number
break  # and start the check from the beginning with next k
else:  # if not...
# check to see if it's divisible by the next odd number.
odds += 2

# if chk isn't divisible by any odds up to the square root of chk
if odds > sqrtk:
primes += 1  # we have a prime number
chk += 2  # check the next odd number to see if it's prime
odds = 3  # and reset odds back to 3 to use it next time

if primes == goal:  # once we've reached the desired amount of prime numbers
return chk - 2

goal = int(input("Enter a number n, 1-1,000,000 to find the nth prime number."))
print("The", goal, "prime number is:", get_nth_prime(goal))


Also, the usage is to write your code "that actually does stuff" behind an if main guard so that you can import your code if you want to re-use your function without having any polluting. In your case, it becomes :

def main():
"""Main function"""
goal = int(input("Enter a number n, 1-1,000,000 to find the nth prime number."))
print("The", goal, "prime number is:", get_nth_prime(goal))

if __name__ == "__main__":
main()


Testing

Having extracted a function to get the n-th prime number, you can more easily write test. You can play it simple, manually :

assert get_nth_prime(1) == 2
assert get_nth_prime(2) == 3


Or you can go further :

assert [get_nth_prime(i) for i in range(1, 100)] == [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523]


Now that we have test cases, rewriting the code is much easier.

A bit of logic

You can rewrite while odds < sqrtk or odds == sqrtk: : while odds <= sqrtk:

Then you can rewrite this using range : while odds < sqrtk or odds == sqrtk: and then the second test can be written using the infamous else on the for loop (the best way to understand it is to read it as nobreak). The code becomes :

        for odds in range(3, int(chk ** .5) + 1, 2):
if chk % odds == 0:  # ...chk is divisible by this odd number....
chk += 2  # then raise the value of chk to the next odd number
break  # and start the check from the beginning with next k
else: # no break => no divisors => prime
primes += 1  # we have a prime number
chk += 2  # check the next odd number to see if it's prime


The check if chk<9 looks like a premature optimisation to me. We can get rid of it.

Then you have :

while primes < goal:
for odds in range(3, int(chk ** .5) + 1, 2):
if chk % odds == 0:  # ...chk is divisible by this odd number....
chk += 2  # then raise the value of chk to the next odd number
break  # and start the check from the beginning with next k
else: # no break => no divisors => prime
primes += 1  # we have a prime number
chk += 2  # check the next odd number to see if it's prime


Then you have chk += 2 that appear in two different places : let's move it to a single place :

while primes < goal:
for odds in range(3, int(chk ** .5) + 1, 2):
if chk % odds == 0:  # ...chk is divisible by this odd number....
break
else: # no break => no divisors => prime
primes += 1
chk += 2

if primes == goal:  # once we've reached the desired amount of prime numbers
return chk - 2


There is no need to compare primes and goal at every single iteration as it won't be updated that often : you can move this to the place where primes is increased :

chk = 5  # the next odd number after 3, which is already taken care of above
primes = 2  # the number of primes recorded, after counting 2 and 3.
while True:
for odds in range(3, int(chk ** .5) + 1, 2):
if chk % odds == 0:  # ...chk is divisible by this odd number....
break
else: # no break => no divisors => prime
primes += 1
if primes == goal:
return chk
chk += 2


More functions

The test of primality can easily be written in a function on its own.

Luckily, I have this ready in my toolbox :

def is_prime(n):
"""Checks if a number is prime."""
if n < 2:
return False
return all(n % i for i in range(2, int(math.sqrt(n)) + 1))

def get_nth_prime(goal):
if goal > 1000000:
return None
if goal == 1:  # first prime is 2
return 2
if goal == 2:  # second prime is 3
return 3

chk = 5  # the next odd number after 3, which is already taken care of above
primes = 2  # the number of primes recorded, after counting 2 and 3.
while True:
if is_prime(chk):
primes += 1
if primes == goal:
return chk
chk += 2


More idiomatic

You are trying to generate prime numbers as you count them. A more pythonic way to do so would be to define a function to generate prime numbers one by one and another one to stop when we've reached what we want to reach. This could look like :

import math
import itertools

def is_prime(n):
"""Checks if a number is prime."""
if n < 2:
return False
return all(n % i for i in range(2, int(math.sqrt(n)) + 1))

def yield_primes():
"""Yields prime number by checking them individually"""
yield 2
yield 3
for i in itertools.count(5, 2):
if is_prime(i):
yield i

def nth(iterable, n, default=None):
"""Returns the nth item or a default value.
From http://stackoverflow.com/questions/12007820/better-ways-to-get-nth-element-from-an-unsubscriptable-iterable ."""
return next(itertools.islice(iterable, n, None), default)

def get_nth_prime(goal):
if goal > 1000000:
return None
return nth(yield_primes(), goal - 1)


I just noticed I've re-used my non efficient is_prime function going through odd and even integers. I'll leave an an exercise to the reader to fun of going only through odd numbers :-)

# Style

The biggest improvement I'd see is your operators need space:

if goal>1000000:
exit()
if goal==1:
print("2")
if goal==2:
print("3")


Would with a little formatting become:

if goal > 1000000:
exit()
if goal == 1:
print("2")
if goal == 2:
print("3")


Your comments are all close to useless.. everybody understanding python (any many people who don't) can easily understand what you are doing there without you telling them again in a tautologic comment...

# Extracting Functions

consider extracting certain functionality to functions (duh!). That's what they are made for. currently your code reads from input, evaluates the input to get a primenumber and then prints to output. This should be at least 3 functions if not more..

Unless there are some additional constraints on the problem, why not essentially jump start the algorithm with some additional hard coded primes so it can start further out and not need to compute the lower primes for every result? Something like this

chk=5         #the next odd number after 3, which is already taken care of above
primes=2    #the number of primes recorded, after counting 2 and 3.
x=0         #the last recorded prime number
if goal >= 100000
primes = 100000
chk = 1299709
while primes<goal:


I've (almost) completely revised the code by adding all prime numbers to a list and by only checking to see if those numbers divide evenly into the number we're checking. It runs much faster but still does not compute 1,000,000 in under 3 minutes.

Also, I want to write this without having to import any libraries. Time is only there for me to test, of course, time.

import time
goal = int(input("Enter a number n, 1-1,000,000 to find the nth prime number."))
start = time.time()
if goal > 1000000:
exit()

if goal > 4:
lst = [2, 3, 5, 7]
chk = 11
primes = 4
while primes < goal:
for n in lst:
if n > chk**.5:
lst.append(chk)
primes += 1
break
if chk % n == 0:
break
chk += 2

else:
print("The", str(goal), "prime number is:", str(chk - 2))

else:
if goal == 1:
print("2")
if goal == 2:
print("3")
if goal == 3:
print("5")
if goal == 4:
print("7")
elapsed = (time.time() - start)
print(elapsed)

• This is a good idea (I didn't want to suggest a too different algorithm). I reckon you could post it as another question to get it reviewed. Also, you should try to take into account comments given by reviewers before posting it as a new answer. – SylvainD Oct 13 '14 at 14:10
• I don't know enough about Python to be confident if chk**.5 gets optimzed out of the loop. If not, you might do the optimization yourself, saving lots of sqaure root computations. Also, are you sur **.5 is precise enough? If for obscure reasons 289**.5 is 16.999999, your code might think 17^2 is a prime – Hagen von Eitzen Oct 13 '14 at 15:15
• while primes <= sqrt(goal) fiddle that somewhere into your code....... – Pieter B Oct 13 '14 at 17:28

I'd suggest using the problem itself to optimize the result by using things you know about the solutions from math itself. In this case, you can start by preprocessing out as many values as possible without checking them directly.

So, for instance, every prime greater than 2 or 3 is of the form 6n + 1 or 6n - 1. (Proof: 6n is divisible by 6; 6n+2 is divisible by 2; 6n + 3 is divisible by 3, and 6n + 4 is divisible by 2; this leaves only 6n + 1 and 6n + 5 == 6(n + 1) - 1.) That will speed up your code by a factor of 3 right there.

You can look at using the Solovay-Strassen test for pseudoprimality if you want to carry this on further: it will eliminate many other false positives, again leaving you with fewer candidates to test.

The following should run through for you (please forgive the C-ish code, I'm still non-python-idiomatic in my coding from years of C++ and C) however it should suffice on a high-spec machine. To properly guarantee the speed you meed you may need to use some multi-threading, and I will look into it as soon as I can.

import sys
import math

def is_prime(num):
for j in range(2,int(math.sqrt(num)+1)):
if (num % j) == 0:
return False;
return True;

def main(argv):
if (len(sys.argv) != 4):
sys.exit('Usage: findNthPrimeInRangeXToY.py <nth_prime> <lower bound> <upper bound>');

i = 0;
store = []
nth = int(sys.argv[1]);
lowBound = int(sys.argv[2]);
highBound = int(sys.argv[3]);
num = lowBound;

while i < nth or num < highBound:
if is_prime(num):
i += 1;
store.append(num);
if i == nth:
print store
print 'The ' + str(nth) + ' prime number is: ' + str(num);
num += 1;

if __name__ == "__main__":
main(sys.argv[1:]);


And here is a small multi-threaded example: it is basic as I dont have access to my main pc at present, however you can use it as a test basis to see which is more performant, single or multiple threads (the code below has been tested at http://www.compileonline.com/execute_python_online.php and seems fine, though I cannot do any proper timing tests using my phone to code):

#!/usr/local/bin/python2.7
import logging
import random
import time

logging.basicConfig(level=logging.INFO,
global number # shared resource
number=None

def makeNumberList(lowBound, highBound):
r = range(lowBound, highBound)
return r

def generate(condition, nlist):
global number

tested=[] # will hold all tested numbers
while True:
condition.acquire()
logging.info("Acquired")
while True:
#number=random.randint(2, 100)
if len(nlist) > 0:
number = nlist.pop()
if number not in tested: # if not tested before
logging.info("New number %d", number)
tested.append(number)
break
condition.notify()
logging.info("Notified")
logging.info("Released")
condition.release()
#time.sleep(1)

def check(condition,nth):
global number
prime=[]
logging.info("Acquired")
condition.acquire()
while len(prime)<nth:
if number==None:
logging.info("Waiting for new number")
condition.wait()
else:
logging.info("testing: %d", number)
divisors=0
divisor=2
while not divisors and  divisor<=number/2:
if number%divisor==0:
divisors+=1
divisor+=1

if not divisors:
logging.info("%d is prime", number)
prime.append(number)
number=None

logging.info("Found prime number %d :  %s" % (nth, str(prime[nth-1]) ))
logging.info("Released")
condition.release()

def main():
numberList = makeNumberList(100,1000000)
numberList.reverse()
nth = 20
#print numberList
g.setDaemon(True)
g.start()
c.start()

if __name__=="__main__":
main()


There are 25 primes below 100, so if you are always going to look for primes over 100, you could simply precalculate the primes in a range, say to 0-1000000 store in an array/file and get the 25+nth entry, which could be the quickest way of the lot, as it is just a read from file and an array lookup. Will try this later on as well:)

• Okay thanks, very interested to hear back on the multi-threading. – DrakkorNoir Oct 14 '14 at 20:20
• you can use primes.utm.edu/nthprime/index.php#nth to verify the nth value as found by the program against the values returned from the site – GMasucci Oct 15 '14 at 11:47
• @DrakkorNoir forgot to post saying a multi-threaded sample was on now:) – GMasucci Oct 17 '14 at 9:13

After taking all the previous answers into consideration and revising my code accordingly, I'm at this:

Instead of creating a list for primes and appending a new prime to it each time one is found, it creates a list of a specific (whatever is necessary) length and replaces each value in the list with whatever prime number was just found. Somewhat faster, but still not fast enough.

import time
goal = int(input("Enter a number n, 1-1,000,000 to find the nth prime number."))
start = time.time()
if goal > 4:
primes = [3]*goal
candidate = 5
list_position = 1
while (list_position + 1) < goal:
limit = int(candidate**.5)
for p in primes:
if candidate % p == 0:
break
if p > limit:
primes[list_position] = candidate
list_position += 1
break

if (candidate + 2) % 3 == 0:
candidate += 4
to_subtract = 4
else:
candidate += 2
to_subtract = 2

else:
if goal == 1:
print("2")
elif goal == 2:
print("3")
print("Prime", str(goal), "is", str(candidate - to_subtract))
elapsed = (time.time() - start)
print(elapsed, "seconds\n")
`