Решета

Здесь мы будем находить все простые числа от $1$ до $n$ .

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

Решето Эратосфена — алгоритм нахождения списка простых чисел.

Идея простая. Запишем ряд чисел $2, 3, 4, \dotsc, n-1, n$ . Вычеркнем из него все числа, делящиеся на $2$ , кроме, конечно, $2$ . Затем вычеркнем все числа, делящиеся на $3$ , кроме $3$ . Число $4$ уже вычеркнуто, и все числа, кратные $4$ , тоже. Поэтому идём дальше. Вычеркиваем все числа, делящиеся на $5$ , кроме $5$ . Ну и продолжаем так, пока не дойдем до конца.

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

Реализовывать программно это можно по-разному, но самый простой способ — завести битовый массив is_prime. Если число $i$ вычеркнуто, то $\code{is\_prime}[i-2] = 0$ . Вообще можно оставить лишние $2$ бита в начале и сделать нормальную индексацию.

input const int n
array[bool] is_prime[n+1] = [true, true, ..., true]

for int i = 2; i <= n; i++:
    if is_prime[i]:
        for int j = 2 * i; j <= n; j += i:
            is_prime[j] = false

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

Во-первых, начинать вычёркивать кратные числа $p$ можно с $p^2$ , а не с $2p$ . Ведь все составные числа, кратные $p$ и меньшие $p^2$ были вычеркнуты до этого, потому что у них был делитель, меньший $p^2/p = p$ .

Во-вторых, внешний цикл можно сделать до $\sqrt{n}$ . Пусть $p$ — простое число, большее $\sqrt{n}$ . Его наименьшее кратное, которое можно вычеркнуть — $p^2$ . Оно будет находиться за диапазоном поиска простых, ведь $p^2 > n$ .

С учётом всех оптимизаций, получаем код

input const int n
array[bool] is_prime[n+1] = [true, true, ..., true]

for int i = 2; i * i <= n; i++:
    if is_prime[i]:
        for int j = i * i; j <= n; j += i:
            is_prime[j] = false

Проанализируем время работы алгоритма. Будем измерять число установок в битовом массиве is_prime.

Для каждого простого числа $p$ в диапазоне от $2$ до $\sqrt{n}$ мы сделаем $\lfloor n / p \rfloor - (p-1)$ установок. Количество чисел в диапазоне от $1$ до $n$ , которые кратны $p$ , равно $\lfloor n/p \rfloor$ . Тогда общее количество установок, сделанное алгоритмом, равно

\sum\limits_{\substack{p ~\text{простое} \\ p \;\! \le \;\! \sqrt{n}}} \Biggl( \left\lfloor \frac{n}{p} \right\rfloor - p + 1 \Biggr) = n \ln \ln n + (M - \ln 2) \cdot n - \frac{n}{\ln n} + O \left( \frac{n}{\ln^2 n} \right)

где $M \approx 0.261\,497$ — константа Мейсселя-Мертенса.

При этом в не оптимизированном алгоритме количество установок равно

\sum\limits_{\substack{p ~\text{простое} \\ p \;\! \le \;\! n}} \Biggl( \left\lfloor \frac{n}{p} \right\rfloor - 1 \Biggr) = n \ln \ln n + M n + O \left( \frac{n}{\ln^2 n} \right)

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

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

Пусть $d(k) \defeq \min\limits_{p ~\text{простое}} \{ p \divides k\}$ — минимальный простой делитель числа $k$ . Любое число $k$ тогда представимо в виде $k = d(k) \cdot r$ , где у $r$ нет простых делителей, меньших $d(k)$ .

Давайте для каждого числа $k$ считать $d(k)$ . Заведем массив d, в котором будем хранить найденные значения.