eratosthenes.md

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

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

Решето Эратосфена (англ. 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)
                prime[j] = false;
    return is_prime;            
}

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

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

Время работы

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

$$ \sum_k \frac{n}{k} = \frac{n}{2} + \frac{n}{3} + \frac{n}{4} + \ldots + \frac{n}{n} = O(n \log n) $$

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

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

1. Простых чисел от $1$ до $n$ примерно $\frac{n}{\ln n}$ .

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

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

$$ \sum_k \frac{1}{\ln k} \frac{n}{k} \approx n \int \frac{1}{k \ln k} = n \ln \ln k \Big |_2^n = O(n \log \log 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$ за время порядка размера этой факторизации:

$$ factor(k) = {d(k)} \cup factor(k / d(k)) $$

Знание факторизации всех чисел — очень полезная информация для некоторых задач. Ленейное решето интересно не своим временем работы, а именно этим массивом минимальных простых делителей.