3 ms·
The fastest variant I know of this algorithm is the one found at https://stackoverflow.com/a/3796442/6899 https://stackoverflow.com/a/3796442/6899 : import
by tzot 3y ago
The fastest variant I know of this algorithm is the one found at https://stackoverflow.com/a/3796442/6899 https://stackoverflow.com/a/3796442/6899 :
import itertools as it
def erat3( ):
D = { 9: 3, 25: 5 }
yield 2
yield 3
yield 5
MASK= 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0,
MODULOS= frozenset( (1, 7, 11, 13, 17, 19, 23, 29) )
for q in it.compress(
it.islice(it.count(7), 0, None, 2),
it.cycle(MASK)):
p = D.pop(q, None)
if p is None:
D[q*q] = q
yield q
else:
x = q + 2*p
while x in D or (x%30) not in MODULOS:
x += 2*p
D[x] = p
- svat 3y agoThis adds two things over the OP's initial version, both mentioned in the post: wheel factorization (with 30), and the "linear probing" to avoid lists. It's possible to keep improving (up to a point) by using e.g. wheel with 210 instead of 30, and so on, if one doesn't mind hard-coding more and more.
- simlevesque 3y agoisn't hardcoding 2 3 and 5 a bit of a cheat ? It seems like you could hardcode it to yield the X next primes and it'd be faster.
- stouset 3y agoThe point isn’t hardcoding those numbers. The point is that you don’t iterate on any multiples of those numbers (which we know are composite) and doing allows us to eliminate 2/3 of the iterations. It’s an extension of enumerating over only odd numbers, which eliminates 1/2 of the iterations. Hardcoding those values is a semi-requirement of the above technique.
- simlevesque 3y agoThank you, it makes more sense now.