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

[…] Optimized one is at: https://unreachable2027.wordpress.com/2012/10/02/python-script-to-find-nth-prime-optimized/ […]

Well, there is an indentantion error at the line with while(1)

It’s working fine here, while is not part of the prime function.