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

Решето Эратосфена работает за $O(n \log \log n)$. Логарифм логарифма — это почти константа, и придираться вроде бы не к чему. Но у алгоритма есть заметный изъян: одно и то же число вычёркивается много раз. Число 60 будет помечено при $p = 2$, при $p = 3$ и при $p = 5$ — три раза вместо одного.

Линейное решето убирает эту избыточность. Каждое составное число помечается ровно однажды, поэтому суммарная работа — честное $O(n)$.

Идея: помечать своим наименьшим простым

Ключ к единственности — договориться, кто именно имеет право вычеркнуть число.

Пусть $\mathrm{lp}[x]$ — наименьший простой делитель числа $x$ (least prime). Любое составное $x$ единственным образом представляется как

$$x = i \cdot p, \qquad p = \mathrm{lp}[x], \qquad i = x / p$$

Раз такое представление одно, то, если каждое число вычёркивать только в этой паре, каждое вычеркнётся ровно один раз. Вся задача — устроить перебор так, чтобы пара $(i, p)$ встречалась ровно однажды.

Код

vector<int> lp(n + 1, 0);   // наименьший простой делитель
vector<int> primes;         // все найденные простые по возрастанию

for (int i = 2; i <= n; i++) {
    if (lp[i] == 0) {       // i не вычеркнули — значит, оно простое
        lp[i] = i;
        primes.push_back(i);
    }
    for (int p : primes) {
        if (p > lp[i] || (long long)i * p > n) break;
        lp[i * p] = p;
    }
}

Внутренний цикл идёт по уже найденным простым от меньших к большим и обрывается по двум условиям. Второе — просто «не вылезли за границу». Первое, p > lp[i], и есть весь алгоритм.

Обратите внимание на (long long)i * p. При $n = 10^6$ произведение доходит до $10^{12}$ и в int не помещается — это классическое место, где решето молча ломается.

Почему каждое число помечается

Возьмём составное $x$ и его наименьший простой делитель $p = \mathrm{lp}[x]$. Положим $i = x / p$.

Все простые делители $i$ не меньше $p$ — иначе у $x$ нашёлся бы простой делитель меньше $p$. Значит, $\mathrm{lp}[i] \ge p$, условие p > lp[i] на этом $p$ ещё не сработало, и цикл до него дойдёт. Также $i \cdot p = x \le n$, так что второе условие тоже выполнено.

Итог: на итерации $i = x/p$ мы обязательно запишем lp[x] = p.

Почему ровно один раз

Предположим, $x$ пометили дважды: как $i_1 \cdot p_1$ и как $i_2 \cdot p_2$.

Условие p <= lp[i] означает, что $p$ не превосходит ни одного простого делителя $i$. Но тогда $p$ — наименьший простой делитель всего произведения $i \cdot p$. То есть в любой помечающей паре $p = \mathrm{lp}[x]$, откуда $p_1 = p_2$, а значит и $i_1 = i_2$.

Пар оказалось не две, а одна. Суммарное число операций равно числу составных чисел до $n$, то есть $O(n)$.

Пример: как заполняется таблица

Первые шаги для $n = 12$:

$i$	$\mathrm{lp}[i]$	что помечаем	почему остановились
2	2 (простое)	$\mathrm{lp}[4] = 2$	$3 > \mathrm{lp}[2] = 2$
3	3 (простое)	$\mathrm{lp}[6] = 2$, $\mathrm{lp}[9] = 3$	$5 > \mathrm{lp}[3] = 3$
4	2	$\mathrm{lp}[8] = 2$	$3 > \mathrm{lp}[4] = 2$
5	5 (простое)	$\mathrm{lp}[10] = 2$	$3 \cdot 5 = 15 > 12$
6	2	$\mathrm{lp}[12] = 2$	$3 > \mathrm{lp}[6] = 2$

Видно главное: на $i = 6$ мы не пометили $6 \cdot 3 = 18$ — не потому, что вышли за границу, а потому, что 18 достанется паре $(9, 2)$, где двойка и есть наименьший делитель.

Что ещё считается тем же циклом

Ценность линейного решета не столько в асимптотике, сколько в том, что вместе с ним почти бесплатно считаются мультипликативные функции. Достаточно знать, как функция ведёт себя на $i \cdot p$ в двух случаях: когда $p \nmid i$ и когда $p \mid i$.

Функция Эйлера — количество чисел от 1 до $x$, взаимно простых с $x$:

phi[1] = 1;
// внутри основного цикла, вместо простого присваивания lp:
if (lp[i] == 0) phi[i] = i - 1;              // i простое
// ...
lp[i * p] = p;
phi[i * p] = (p == lp[i]) ? phi[i] * p : phi[i] * (p - 1);

Так же считаются число делителей, сумма делителей, функция Мёбиуса. Все — за один проход, без отдельного решета на каждую.

И, конечно, массив $\mathrm{lp}$ сам по себе даёт разложение любого числа до $n$ за $O(\log x)$: делим на $\mathrm{lp}[x]$, пока не дойдём до единицы.

Честное сравнение с Эратосфеном

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

Причина — кэш. Эратосфен идёт по массиву строго по возрастанию с постоянным шагом: процессор угадывает такой доступ и подгружает данные заранее. Линейное решето прыгает по адресам $i \cdot p$ для разных $p$ и вдобавок читает массив primes, то есть работает с памятью в двух местах сразу. Константа получается больше, и на $n$ до $10^7$ выигрыш асимптотики её не окупает.

Практический вывод:

• нужен только список простых — берите Эратосфена, он проще и обычно быстрее;
• нужен $\mathrm{lp}$ или мультипликативная функция — берите линейное;
• знать нужно оба: на собеседовании и на олимпиаде спрашивают именно про второе.

Память у линейного решета тоже больше: int на число вместо bool, то есть в 4 раза (а с учётом того, что vector<bool> упакован по битам, — в 32). При $n = 10^8$ это уже решает.