Python script to find Nth prime – optimized

Fork me on GitHub
Based on the fact, that it is enough to find factors till the square root of a number to determine whether a number is a prime or not.
Since, for every a*b=number, one number is less than square root and other is greater than square root of the number. and when a=b it is the square of the number.
This code prints the time taken to calculate the n th prime. When I first started blogging I wrote a naive program to find nth prime. That takes very much time for larger n. You can check that one @
https://unreachable2027.wordpress.com/2011/03/20/python-script-to-find-nth-prime/

Fork prime repository in GitHub

from math import sqrt
import time
s=time.time()
num=1
pcnt=0
def prime(n):
    sqroot=int(sqrt(n))
    j=2
    while j<=sqroot:
        if n%j==0:
            return False
        j=j+1
    return True

while(1):
    num=num+1
    if prime(num):
        pcnt=pcnt+1
    if pcnt==100000:
        print pcnt,'th prime is',num
        break

print time.time()-s

Advertisements

3 thoughts on “Python script to find Nth prime – optimized

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s