Fast nth prime in Python using trial division

Question

I'm trying to speed this code up for larger values of N. Any suggestions? I'd like to stick to this implementation and not move on to something more complex like numpy or sieves. Is there any low hanging performance I'm missing?

import time 
start = time.clock()
def prime(num, divs):
 prev = 1
 if divs:
 for x in divs:
 if num % x == 0:
 return False
 if num/x < prev:
 break
 prev = x
 return True
i = 0
j = 2
k = []
while i != 50000:
 if prime(j, k) == True:
 k.append(j)
 i += 1
 #if i % 50000 == 0:
 # print (i)
 j += 1
print ("Done", j)
print ("Time", time.clock()-start)
time.sleep(50)

Answer 1

Division is a comparatively expensive operation, and it accounts for the lion's share of the time taken by trial division. Hence there are two major routes for improving efficiency:

• reduce the cost of divisions by replacing them with multiplications
• reduce the number of divisions by filtering candidates efficiently

Replacing divisions as a means of divisibility testing (i.e. x % p == 0) with multiplicatoin (x * MINV <= QMAX) gives a seven-fold speed increase in C++, but in Python it will be a lot less because of the interpreter overhead.

'Filtering candidates' means eliminating multiples of small primes during enumeration of the candidates that will be subjected to trial division. The most famous variant is skipping multiples of two (a.k.a. 'odds-only' or 'mod 2 wheel'), but also fairly well known - often under almost superstitious guises - is the mod 6 wheel that steps in the rhythm 4,2,4,2,... A further savings comes from the fact that the small primes skipped during enumeration can also be skipped during trial division. That is, when candidates are stepped mod 6 then the trial division would start with the prime 5, not 2.

Benchmarks, detailed explanations - and links to even more detailed explanations including papers - are in my answer to

• Prime sieve implementation (using trial division) in C++

Code in that topic is in C++ and C#, but the principles and techniques apply to any language.