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 sqrtdef isprime(n):    for i in range(2,int(sqrt(n))+1):        if n%i==0:            return False    return Truedef 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 ansIt 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 sqrtdef 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 listThe \$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?
Computing the n-th prime
python;performance;python 3.x;primes
SuperBiasedMan made a very good answer.However there is still a performance problem with the cache/list.Lets say we are finding the 11th prime. We will have the following cache:[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]The 11th prime is 31. But we will check against 29,even though we know that can't be a factor until the number becomes 58.What I'm trying to say is, your first function will only try up to \$\sqrt{31}\$,where your new function tries up to \$31\$.A simple 'I'm no mathematician' approach to fix this is to just filter the list.sqrt = math.sqrt(m)for prime in (i for i in list if i <= sqrt):    # The restThis however suffers from the problem of testing all the numbers too.However rather than the test being m % prime == 0, it is now i <= sqrt.To fix this you can create a generator, and break at i > sqrt.def filter_cache(num, cache):    sqrt = math.sqrt(num)    for prime in cache:        if prime > sqrt:            break        yield primefor prime in filter_cache(m, list):    # The restThis should be faster than both methods.However your first 'naive' approach will be faster at small numbers.There is an improved version of the naive program, where you count in steps of 6.And check either side of that number, so \$6n-1\$ and \$6n+1\$.Thank you  JDugosz for the algorithm.This algorithm means that there is 1/3 less checks to make.However you will need to start with a cache / list pre-generated with [2, 3].I use SuperBiasedMan's cache optimization.def prime(wanted_index, cache=[2, 3]):    try:        return cache[wanted_index - 1]    except IndexError:        pass    def filter_cache(num):        sqrt = math.sqrt(num)        for prime in cache:            if prime > sqrt:                break            yield prime    def add_prime(num):        for prime in filter_cache(num):            if num % prime == 0:                return index        cache.append(num)        return index + 1    index = len(cache)    prime_counter = (        0        if index == 2 else            cache[-1] + 1            if (cache[-1] + 1) % 6 == 0 else            cache[-1] - 1    )    while index < wanted_index:        prime_counter += 6        index = add_prime(prime_counter - 1)        index = add_prime(prime_counter + 1)    return cache[wanted_index - 1]Even though it is quite large it's quite simple.The only strange part would be add_prime.This is as it takes a number, and if it is prime adds it to the cache.The special part about this is that cache.append modifies prime's cache.However if we were to do index += 1 we would get UnboundLocalError.