I've written some Python 3 code that computes the \$n\$-th prime. I implemented first a naive isprime function that looks for divisors of \$m\$ between \$2\$ and \$\lfloor \sqrt m \rfloor+1\$. Then a loop looks for primes and stops when the \$n\$th one is found.
from math import sqrt
def isprime(n):
for i in range(2,int(sqrt(n))+1):
if n%i==0:
return False
return True
def prime(n):
m=3
i=2
ans=3
while i<=n:
if isprime(m):
i=i+1
ans=m
m=m+2
else:
m=m+2
return ans
It occured to me that prime performs a lot of unnecessary computations: for a given \$m\$, it checks if composite numbers (like 14,16) divide \$m\$. That is useless, and it would be more efficient to look only for prime divisors of \$m\$. This led me to some "storage" approach, where I maintain a list of all the primes I've found, and use them to test for divisors of the next numbers.
from math import sqrt
def prime(n):
list=[2]
i=1
m=3
while i<n:
flag=0
for p in list:
if m%p==0:
flag=1
break
else:
continue
if flag==0:
list.append(m)
m=m+2
i=i+1
else:
m=m+2
return list
The \$n\$th prime is given by prime(n)[-1]
I have an issue with the performance of the second code: it's really slow.
On my computer, according to the Unix command time python code.py
, computing the \$6000\$-th prime with the first code takes \$0.231\$ seconds, and \$2.799\$ seconds with the other approach!
Why is the clever way slower than the naive one?