Определение. Целое положительное число называется простым, если оно имеет ровно два различных натуральных делителя — единицу и самого себя. Единица простым числом не считается.
Решето Эратосфена (англ. 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\) до \(n\) примерно \(\frac{n}{\ln n}\) .
Простые числа распределены без больших «разрывов» и «скоплений», то есть \(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)) \]
Знание факторизации всех чисел — очень полезная информация для некоторых задач. Ленейное решето интересно не своим временем работы, а именно этим массивом минимальных простых делителей.