Решето Эратосфена и линейное решето

Решето Эратосфена и линейное решето: как за один проход узнать всё про простоту чисел до миллионов.

Решето Эратосфена — алгоритм, который находит все простые числа на отрезке [2; n] за O(n·log log n), вычёркивая кратные каждого найденного простого.

Зачем это в олимпиадах

Проверять каждое число по отдельности за O(√n) хорошо для единичного запроса. Но когда нужно узнать простоту всех чисел до миллиона или быстро факторизовать тысячи чисел в запросах, проверка по одному становится слишком медленной. Решето готовит ответы для всего диапазона разом. Это рабочая лошадка задач вроде «сколько простых на отрезке», «сумма простых до n», предподсчёта для функции Эйлера или количества делителей. Без решета олимпиадная теория чисел немыслима.

Идея решета Эратосфена «на пальцах»

Выпишем все числа от 2 до n. Первое невычеркнутое — 2, оно простое. Вычеркнем все его собственные кратные: 4, 6, 8, … Следующее невычеркнутое — 3, простое; вычеркнем 6, 9, 12, … (6 уже вычеркнуто — не страшно). Так продолжаем: каждое первое уцелевшее число простое, а все его кратные — составные. К концу прохода уцелели ровно простые.

Две оптимизации делают решето быстрым. Во-первых, внешний цикл достаточно вести до √n: у любого составного m ≤ n есть простой делитель не больше √n, так что к моменту i > √n все составные уже вычеркнуты. Во-вторых, вычёркивание кратных простого i можно начинать не с 2i, а с i·i: меньшие кратные (2i, 3i, …) уже вычеркнуты при обработке меньших простых.

def sieve(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False
    i = 2
    while i * i <= n:
        if is_prime[i]:
            # начинаем с i*i и шагаем по i
            for j in range(i * i, n + 1, i):
                is_prime[j] = False
        i += 1
    return is_prime

primes_flags = sieve(30)
print([i for i in range(31) if primes_flags[i]])
print(sum(primes_flags))  # сколько простых до 30

Вывод:

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
10

Почему сложность — O(n log log n)

Для каждого простого p мы делаем примерно n/p вычёркиваний. Суммарно это n · ∑ 1/p по всем простым p ≤ n. Знаменитый результат теории чисел гласит, что сумма обратных к простым растёт как ln ln n. Отсюда оценка O(n·log log n) — практически линейная: log log n для n = 10⁶ меньше 3. Поэтому решето до миллиона работает за доли секунды.

Решето с наименьшим простым делителем (для факторизации)

Часто нужно не просто знать простоту, а быстро факторизовать числа. Слегка изменим решето: будем хранить для каждого числа его наименьший простой делитель (SPF — smallest prime factor). Тогда факторизация любого числа — это спуск по SPF за O(log n) делений.

def smallest_prime_factors(n):
    spf = list(range(n + 1))   # spf[x] = x по умолчанию
    i = 2
    while i * i <= n:
        if spf[i] == i:        # i простое
            for j in range(i * i, n + 1, i):
                if spf[j] == j:  # ещё не отмечено меньшим делителем
                    spf[j] = i
        i += 1
    return spf

spf = smallest_prime_factors(100)

def factorize_fast(x, spf):
    factors = {}
    while x > 1:
        p = spf[x]
        while x % p == 0:
            factors[p] = factors.get(p, 0) + 1
            x //= p
    return factors

print(factorize_fast(84, spf))   # 84 = 2^2 * 3 * 7
print(factorize_fast(97, spf))   # 97 простое

Вывод:

{2: 2, 3: 1, 7: 1}
{97: 1}

Линейное решето

Классическое решето вычёркивает некоторые составные числа по несколько раз (12 вычёркивается и через 2, и через 3). Линейное решето устроено так, что каждое составное вычёркивается ровно один раз — отсюда строгая линейность O(n). Ключевая идея: каждое составное число вычёркивается через свой наименьший простой делитель. Мы поддерживаем список найденных простых и для текущего i вычёркиваем произведения i · p, останавливаясь, как только p делит i.

def linear_sieve(n):
    spf = [0] * (n + 1)
    primes = []
    for i in range(2, n + 1):
        if spf[i] == 0:        # i простое
            spf[i] = i
            primes.append(i)
        for p in primes:
            if p > spf[i] or i * p > n:
                break
            spf[i * p] = p     # p — наименьший простой делитель i*p
    return primes, spf

primes, spf = linear_sieve(30)
print(primes)
print(spf[12], spf[15], spf[17])  # наименьшие простые делители

Вывод:

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
2 3 17

Условие p > spf[i] (точнее, p делит i) — сердце алгоритма: оно гарантирует, что i·p вычёркивается именно через свой наименьший простой делитель p и больше никогда. На практике линейное решето выигрывает у обычного не столько по скорости (константа решета Эратосфена меньше), сколько тем, что попутно строит SPF для мгновенной факторизации и легко обобщается на мультипликативные функции.

Разбор задачи: количество и сумма простых на отрезке

Типовой запрос: «сколько простых не превосходит n и какова их сумма». С решетом это пара строк: построили массив флагов, прошлись, посчитали. Префиксные суммы по флагам позволяют отвечать на много запросов «сколько простых в [1, k]» за O(1) после предподсчёта — приём, который экономит время в задачах с множеством запросов.

def sieve(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False
    i = 2
    while i * i <= n:
        if is_prime[i]:
            for j in range(i * i, n + 1, i):
                is_prime[j] = False
        i += 1
    return is_prime

n = 50
is_prime = sieve(n)
# префиксное количество простых: prime_count[k] = сколько простых в [0, k]
prime_count = [0] * (n + 1)
for k in range(1, n + 1):
    prime_count[k] = prime_count[k - 1] + (1 if is_prime[k] else 0)

print("Простых до 50:", prime_count[50])
print("Простых в [10, 30]:", prime_count[30] - prime_count[9])
print("Сумма простых до 50:", sum(i for i in range(n + 1) if is_prime[i]))

Вывод:

Простых до 50: 15
Простых в [10, 30]: 6
Сумма простых до 50: 328

Префиксный массив prime_count превращает запрос «сколько простых в отрезке [l, r]» в одно вычитание prime_count[r] − prime_count[l−1] за O(1). Это стандартная связка «решето + префиксные суммы», которой решается целый класс задач про распределение простых.

Подводные камни

• Память. Решето хранит массив на n+1 элементов. До 10⁷ ещё помещается, дальше нужен сегментированный вариант или битовое решето.
• Начинать с i*i, не с 2*i. Иначе теряется главная константа ускорения (хотя корректность сохраняется).
• В линейном решете break обязателен. Без условия остановки оно перестаёт быть линейным и может вычёркивать неверно.
• Индекс 0 и 1. Всегда явно помечайте их как «не простые».

Итог

• Решето Эратосфена находит все простые до n за O(n·log log n) — почти линейно.
• Оптимизации: внешний цикл до √n, вычёркивание с i·i.
• Массив SPF позволяет факторизовать любое число за O(log n).
• Линейное решето вычёркивает каждое составное ровно раз и попутно даёт SPF.