from itertools import accumulate, chain, cycle, islice, takewhile
INITIAL = [2, 3, 5, 7, 11]
STEPS = [2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 6, 6, 2, 6, 4, 2, 6, 4, 6, 8, 4, 2, 4, 2, 4, 8,
6, 4, 6, 2, 4, 6, 2, 6, 6, 4, 2, 4, 6, 2, 6, 4, 2, 4, 2, 10, 2, 10]
def gencand():
return chain(INITIAL[1:-1], accumulate(chain(INITIAL[-1:], cycle(STEPS))))
def toindex(i: int): return i // 2 - 2
def fromindex(idx: int): return idx * 2 + 5
def eratosthenes(end):
prime = [True] * toindex(end)
for i in takewhile(end.__gt__, gencand()):
if not prime[toindex(i)]: continue
for j in range(i * i, end, i * 2): prime[toindex(j)] = False
return prime
print(*INITIAL[:2], ' '.join(islice((str(fromindex(n)) for n, b in enumerate(eratosthenes(8000)) if b), 998))) Храним флаги только для нечётных чисел, начиная с 5. Кандидаты на простоту вычисляются через кольцо шагов, из которого убраны числа, кратные 2, 3, 5 и 7. Остаётся порядка 22% чисел, которые мы перебираем.
На ленивых генераторах всё было бы быстрее, и не надо было бы хранить массив. Но в Питоне они сделаны немного не так, как надо, так что я ещё не придумал, как это в нём реализовать (через tee получается медленно и громоздко, наверное, придётся искать генератор в стиле Хаскеля или делать свой).
Конечная точка для перебора определяется решением уравнения
π(n) = n / ln n
n - искомая точка
π(n) - количество простых чисел, в данном случае - 1000 Для нашего случая n ≲ 9120, но плотность простых чисел падает с увеличением n, поэтому можно взять чуть меньше. Практика показывает, что 8000 хватает.
