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= 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?