Самый быстрый метод, который я пробовал до сих пор, основан на функции кулинарной книги Python erat2
:
import itertools as it
def erat2a( ):
D = { }
yield 2
for q in it.islice(it.count(3), 0, None, 2):
p = D.pop(q, None)
if p is None:
D[q*q] = q
yield q
else:
x = q + 2*p
while x in D:
x += 2*p
D[x] = p
См. этот ответ для объяснения ускорения.