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
Code in that topic is in C++ and C#, but the principles and techniques apply to any language.