Решето Эратосфена

Решето Эратосфена (sieve of Eratosthenes) находит все простые числа от 2 до N за $O(N\log \log N)$: каждое найденное простое вычёркивает свои кратные.

Зачем нужно

Задача: N — натуральное число, найти все простые $p\le N$.

Не из лекции: сравнение с проверкой по одному

Проверить одно число на простоту можно за $O(\sqrt{N})$ — см. L01. Если проверять так каждое число до N, выйдет $O(N\sqrt{N})$. Решето не проверяет числа по одному, а сразу вычёркивает все составные — почти линейно.

Как работает

Таблица is_prime на $N+1$ элемент, сначала всё ✓, 0 и 1 — ✗. Идём по $d=2,3,\dots ,N$:

• is_prime[d] = ✗ — $d$ составное, пропускаем;
• is_prime[d] = ✓ — $d$ простое, вычёркиваем $2d,3d,4d,\cdots \le N$.

is_prime = [T, T, ..., T]              // N + 1 элемент
is_prime[0] = is_prime[1] = F
for d = 2 ... N
    если is_prime[d] = T               // d — простое
        m = 2
        while (m * d ≤ N)
            is_prime[m * d] = F
            m++
for d = 2 ... N
    если is_prime[d] = T
        print(d)

Здесь 2 ... N включает N.

Почему верно

Не из лекции: корректность

Вычёркиваются только числа $m\cdot d$ с $m,d\ge 2$ — составные. Любое составное $k$ вычеркнет его наименьший делитель $d>1$: этот делитель простой, и при нём $m$ дойдёт до $k/d$.

Когда цикл доходит до $d$, is_prime[d] уже окончательный: если $d$ составное, его наименьший простой делитель меньше $d$ и уже успел его вычеркнуть. Алгоритм опирается на таблицу, которую сам же строит.

Оценки

На лекции: $T(N)=O(N\log \log N)$, без доказательства.

Не из лекции: откуда $\log \log N$ и память

Для простого $d$ внутренний цикл делает меньше $N/d$ шагов, поэтому $T(N)=O\left(N{\sum }_{p\le N}\frac{1}{p}\right)$. Сумма обратных простых растёт как $\log \log N$. Доказательство — в конспекте L03.

Если бы вычёркивали кратные каждого $d$, а не только простого, получилось бы $N(\frac{1}{2}+\frac{1}{3}+\cdots +\frac{1}{N})\le N\ln N$.

Память — таблица на $N+1$ элемент: $M(N)=O(N)$.

Тонкости

• $\log \log N$ растёт очень медленно: при $N=10^8$ это около 2,9. На практике решето работает почти как линейный проход.
• Память $O(N)$ — ограничение: решето до $10^9$ требует гигабайт таблицы (по байту на число).
• Проверку is_prime[d] нельзя убирать: без неё составные $d$ тоже вычёркивали бы кратные, и время выросло бы до $O(N\log N)$. Ответ при этом остался бы верным.

Частые ошибки

• Таблица на N элементов вместо $N+1$: само N не помещается.
• Забыть is_prime[0] = is_prime[1] = F — 0 и 1 окажутся «простыми».
• Цикл вывода for d = 2 ... N без самого N — простое N потеряется.