10
\$\begingroup\$

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
\$\endgroup\$
10
\$\begingroup\$

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

This is getting into more advanced Python stuff so you might want to read a bit more about this.

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 :-)

\$\endgroup\$
6
\$\begingroup\$

Style

Your code is screaming for whitespace and proper indentation. Please read the python styleguide PEP-8

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")

Comments:

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..

\$\endgroup\$
2
\$\begingroup\$

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: 
\$\endgroup\$
1
\$\begingroup\$

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)
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – SylvainD Oct 13 '14 at 14:10
  • \$\begingroup\$ 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 \$\endgroup\$ – Hagen von Eitzen Oct 13 '14 at 15:15
  • \$\begingroup\$ while primes <= sqrt(goal) fiddle that somewhere into your code....... \$\endgroup\$ – Pieter B Oct 13 '14 at 17:28
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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 threading
import logging
import random
import time

logging.basicConfig(level=logging.INFO,
                    format="[%(threadName)-14s] %(message)s")
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
    condition=threading.Condition()
    g=threading.Thread(name="GenerateThread",target=generate, args=(condition,numberList, ))
    c=threading.Thread(name="CheckThread",target=check, args=(condition, nth,))
    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:)

\$\endgroup\$
  • \$\begingroup\$ Okay thanks, very interested to hear back on the multi-threading. \$\endgroup\$ – DrakkorNoir Oct 14 '14 at 20:20
  • \$\begingroup\$ 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 \$\endgroup\$ – GMasucci Oct 15 '14 at 11:47
  • \$\begingroup\$ @DrakkorNoir forgot to post saying a multi-threaded sample was on now:) \$\endgroup\$ – GMasucci Oct 17 '14 at 9:13
0
\$\begingroup\$

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")
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.