Решето Эратосфена: как вычеркнуть всё лишнее и оставить простые

Чтобы найти все простые числа до миллиона, не нужно проверять ни одно из них на простоту — достаточно вычеркнуть все составные.

Эратосфен, заведовавший Александрийской библиотекой, ещё и довольно точно измерил длину окружности Земли. Решето — лишь одна из его идей.

В чём сложность с простыми числами

Простое число делится только на 1 и на себя. Проверить одно число «в лоб» — перебрать делители; но если нужно найти все простые до большого $N$, проверка каждого по отдельности расточительна. Эратосфен предложил вывернуть задачу наизнанку: вместо «какие числа простые?» спросить «какие числа точно составные?» — и вычеркнуть именно их.

Идея: вычёркиваем кратные

Выписываем все числа от 2 до $N$. Первое невычеркнутое — 2, оно простое. Теперь вычёркиваем все его кратные: 4, 6, 8, 10… Следующее уцелевшее — 3, тоже простое; вычёркиваем 6, 9, 12, 15… Число 4 уже вычеркнуто (как кратное 2) — пропускаем. Берём 5, вычёркиваем его кратные. И так далее. То, что осталось невычеркнутым, — и есть все простые числа. Ни одного деления, только сложение шага и пометки. Название «решето» (sieve) ровно об этом: составные числа «проваливаются», простые остаются на сите.

def sieve(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False
    p = 2
    while p * p <= n:          # хватит дойти до корня из n
        if is_prime[p]:
            # вычёркиваем с p*p: меньшие кратные уже вычеркнуты
            for multiple in range(p * p, n + 1, p):
                is_prime[multiple] = False
        p += 1
    return [i for i in range(2, n + 1) if is_prime[i]]

primes = sieve(50)
print(primes)
print(f"Простых до 50: {len(primes)}")
print(f"Простых до 1000: {len(sieve(1000))}")

Две тонкости, которые экономят время

Первое: начинать вычёркивание кратных числа $p$ можно не с $2p$, а сразу с $p^2$. Почему? Все кратные $p$, что меньше $p^2$ (например, $2p$, $3p$), имеют меньший множитель и потому уже вычеркнуты на предыдущих шагах. Это заметно ускоряет работу.

Второе: внешний цикл можно остановить, когда $p^2 \gt N$, то есть при $p \gt \sqrt{N}$. Если число $m \le N$ составное, у него обязательно есть делитель, не превосходящий $\sqrt{m} \le \sqrt{N}$ — иначе произведение двух делителей, каждый больше корня, превысило бы $N$. Значит, к моменту $p = \sqrt{N}$ всё составное уже вычеркнуто.

$$\text{если } m = a \cdot b \text{ и } a \le b, \text{ то } a \le \sqrt{m}$$

Насколько это быстро

Суммарное число вычёркиваний оценивается как $N \cdot (\frac{1}{2} + \frac{1}{3} + \frac{1}{5} + \dots)$ по простым, а эта сумма растёт как $\ln \ln N$ — крайне медленно. Итоговая сложность $O(N \log \log N)$ практически неотличима от линейной. Для миллиона чисел решето отрабатывает за доли секунды на любом ноутбуке.

Где встречается

Решето — рабочая лошадка везде, где нужны простые «оптом»: предвычисление таблиц для факторизации, теоретико-числовые задачи, олимпиадное программирование. Для одного очень большого числа на простоту его не применяют (там нужны вероятностные тесты вроде Миллера — Рабина), но для «всех простых до N» оно почти непобедимо. Существуют и более хитрые линейные варианты, но классическое решето остаётся эталоном простоты и скорости.

Мораль

Решето Эратосфена учит важному приёму: иногда легче описать, что точно не подходит, чем проверять каждого кандидата. Замена прямого вопроса на отсев лишнего превращает дорогую проверку простоты в дешёвое вычёркивание. И снова древняя идея оказывается живее многих современных.