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) — начинай с неё, решето подключай, только если реально упёрся в скорость.

Когда перебор медленный — ускорение решетом — Задание 25 ЕГЭ 2027 | Методички — Профиматика