7 Когда перебор медленный — ускорение решетом
Когда перебор медленный — ускорение решетом
Рекурсивная функция p(x) для чисел порядка миллиарда работает быстро: наименьший делитель ищется лишь до √x (это ~50 000 шагов в худшем случае, а обычно куда меньше). Первых пять чисел программа находит за секунды-десятки секунд — этого достаточно.
Если же диапазон огромный и перебор всё-таки не успевает, множители-кандидаты можно заранее подготовить решетом Эратосфена — списком простых до √(макс. числа):
def sieve(N):
prime = [True] * (N + 1)
prime[0] = prime[1] = False
for i in range(2, int(N**0.5) + 1):
if prime[i]:
for j in range(i * i, N + 1, i):
prime[j] = False
return primeНо для типовых задач 2026 года хватает рекурсивной p(x) — начинай с неё, решето подключай, только если реально упёрся в скорость.