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

Определение. Целое положительное число называется простым, если оно имеет ровно два различных натуральных делителя — единицу и самого себя. Единица простым числом не считается.

Решето Эратосфена (англ. sieve of Eratosthenes) — алгоритм нахождения всех простых чисел от $1$ до $n$.

Основная идея соответствует названию алгоритма: запишем ряд чисел $1, 2,\ldots, n$, а затем будем вычеркивать

• сначала числа, делящиеся на $2$, кроме самого числа $2$,
• потом числа, делящиеся на $3$, кроме самого числа $3$,
• с числами, делящимися на $4$, ничего делать не будем — мы их уже вычёркивали,
• потом продолжим вычеркивать числа, делящиеся на $5$, кроме самого числа $5$,

…и так далее.

Самая простая реализация может выглядеть так:

vector<bool> sieve(int n) {
    vector<bool> is_prime(n + 1, 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;
    return is_prime;            
}

Этот код сначала помечает все числа, кроме нуля и единицы, как простые, а затем начинает процесс отсеивания составных чисел. Для этого мы перебираем в цикле все числа от $2$ до $n$, и, если текущее число простое, то помечаем все числа, кратные ему, как составные.

Если память позволяет, то для оптимизации скорости лучше использовать не вектор bool, а вектор char — но он займёт в 8 раз больше места. Компьютер не умеет напрямую оперировать с битами, и поэтому при индексации к vector<bool> он сначала достаёт нужный байт, а затем битовыми операциями получает нужное значение, что занимает приличное количество времени.

#Время работы

Довольно легко показать, что асимптотическое время работы алгоритма хотя бы не хуже, чем $O(n \log n)$: даже если бы мы входили в цикл вычёркиваний для каждого числа, не проверяя его сначала на простоту, суммарно итераций было бы

Здесь мы воспользовались асимптотикой гармонического ряда.

У исходного алгоритма асимптотика должна быть ещё лучше. Чтобы найти её точнее, нам понадобятся два факта про простые числа:

1. Простых чисел от $1$ до $n$ примерно $\frac{n}{\ln n}$ .
2. Простые числа распределены без больших «разрывов» и «скоплений», то есть $k$-тое простое число примерно равно $k \ln k$.

Мы можем упрощённо считать, что число $k$ является простым с «вероятностью» $\frac{1}{\ln n}$. Тогда, время работы алгоритма можно более точнее оценить как

Асимптотику алгоритма можно улучшить и дальше, до $O(n)$.

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

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

Обозначим за $d(k)$ минимальный простой делитель числа $k$ и заметим следующий факт: у составного числа $k$ есть единственное представление $k = d(k) \cdot r$, и при этом у числа $r$ нет простых делителей меньше $d(k)$.

Идея оптимизации состоит в том, чтобы перебирать этот $r$, и для каждого перебирать только нужные множители — а именно, все от $2$ до $d(r)$ включительно.

#Алгоритм

Немного обобщим задачу — теперь мы хотим посчитать для каждого числа $k$ на отрезке $[2, n]$ его минимальный простой делитель $d_k$, а не только определить его простоту.

Изначально массив $d$ заполним нулями, что означает, что все числа предполагаются простыми. В ходе работы алгоритма этот массив будет постепенно заполняться. Помимо этого, будем поддерживать список $p$ всех найденных на текущий момент простых чисел.

Теперь будем перебирать число $k$ от $2$ до $n$. Если это число простое, то есть $d_k = 0$, то присвоим $d_k = k$ и добавим $k$ в список $p$.

Дальше, вне зависимости от простоты $k$, начнём процесс расстановки значений в массиве $d$ — переберем найденные простые числа $p_i$, не превосходящие $d_k$, и сделаем присвоение $d_{p_i k} = p_i$.

const int n = 1e6;

int d[n + 1];
vector<int> p;
 
for (int k = 2; k <= n; k++) {
    if (p[k] == 0) {
        d[k] = k;
        p.push_back(k);
    }
    for (int x : p) {
        if (x > d[k] || x * d[k] > n)
            break;
        d[k * x] = x;
    }
}

Алгоритм требует как минимум в 32 раза больше памяти, чем обычное решето, потому что требуется хранить делитель (int, 4 байта) вместо одного бита на каждое число. Линейное решето хоть и имеет лучшую асимптотику, но на практике проигрывает также и по скорости оптимизированному варианту решета Эратосфена.

#Применения

Массив $d$ позволяет искать факторизацию любого числа $k$ за время порядка размера этой факторизации: