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

Материал из Algocode wiki
Перейти к: навигация, поиск

Решето Эратосфена — алгоритм нахождения всех простых чисел от $1$ до $n$ за $O(n \cdot \log{\log{n}})$ или за $O(n)$ в зависимости от реализации.

Основная идея

Запишем все числа от $2$ до $n$ ($1$ - не простое). Затем будем вычеркивать:

  • числа, кратные $2$, кроме самого числа $2$
  • числа, кратные $3$, кроме самого числа $3$
  • числа, кратные $4$, не трогаем, так как они, как и само число $4$, были вычеркнуты ранее
  • числа, кратные $5$, кроме самого числа $5$

и так до $n$.

Простейшая реализация данного алгоритма будет выглядеть примерно так:

 1 vector<bool> primes(int n) {
 2     vector<bool> prime(n + 1, true);
 3     prime[0] = prime[1] = false;
 4     for (int i = 2; i <= n; ++i)
 5         if (prime[i])
 6             for (int j = 2 * i; j <= n; j += i)
 7                 prime[j] = false;
 8 
 9     return prime;
10 }

Функция помечает сначала все числа как простые, вычеркивает $0$ и $1$ (они не простые), а затем для каждого числа $i$ от $2$ до $n$, если оно простое, вычеркивает все числа, кратные ему (кроме него самого).

Оптимизации

  • Если нет жестких требований по памяти, лучше использовать vector<char>, так как vector<bool> размера $n$ упаковывается компьютером в $\lceil{\frac{n}{8}}\rceil$ байт, и последующие обращения к элементам получаются долгими.
  • Нетрудно понять, что если $x$ составное, то оно будет вычеркнуто его минимальным простым делителем. В функции выше в случае, если $i$ простое, мы вычеркивали числа, кратные $i$, начиная от $2 \cdot i$. Теперь мы можем вычеркивать числа, начиная с $i^2$, так как все меньшие кратные $i$ числа были вычеркнуты ранее.

Итоговая реализация требует совсем мало изменений и остается читателю в качестве упражнения.

Асимптотика

Для начала несложно показать, что время работы хотя бы не хуже $O(n \cdot \log{n})$. Предположим, мы начинаем вычеркивать числа, кратные $i$, для каждого $i$ (вне зависимости от того, было ли $i$ вычеркнуто ранее как составное). Тогда время работы алгоритма будет: $$\sum_{k=2}^{n}{\frac{n}{k}} = \frac{n}{3} + \frac{n}{4} + ... + \frac{n}{n - 1} + \frac{n}{n} = O(n \cdot \log{n})$$ Тут мы использовали сумму гармонического ряда. Но вычеркивать мы начинаем только от простых чисел, поэтому асимптотика должна быть еще лучше. Для дальнейших рассуждений необходимы 2 факта:

  • простых чисел от $1$ до $n$ примерно $\frac{n}{\ln{n}}$
  • $k$-е простое число приблизительно равно $k \cdot \ln{k}$

Будем упрощенно считать, что число является простым с вероятностью $\frac{1}{\ln{n}}$. Тогда время работы можно оценить как ALARM : оценка на коленке. Приблизим искомую сумму интегралом соответствующей функции. Перебираем числа $k$ от $1$ до $n/\ln n$, затем $k$-ое простое число примерно равно $k\ln k$, поэтому мы сделаем $\dfrac{n}{k\ln k}$ шагов по массиву. (Перейдем от последовательность $a_n$ к функции $f: f(n) = a_n$). \begin{multline} \sum \limits_{k = 2}^{n/\ln n}a_n = \sum \limits_{k=2}^{n/\ln n} \dfrac{n}{k\ln k} \\ \int_2^{n/\ln n} \dfrac{n}{x\ln x}dx = n\int_2^{n/\ln n}\dfrac{d(\ln x)}{\ln x} = n\int_2^{n/\ln n}d(\ln \ln x) = O\left( n \ln \ln \dfrac{n}{\ln n}\right) = O(n\ln \ln n) \\ \end{multline}

Линейное время работы

Тот факт, что мы можем пометить число как составное несколько раз (столько, сколько у него различных простых делителей), мешает нам добиться асимптотики $O(n)$. Придумаем, как помечать любое составное число ровно один раз.

Пусть $p[x]$ - минимальный простой делитель числа $x$. Заметим, что любое число $x$ можно представить в виде $x = p[x] * i$. При этом очевидно, что $p[x] \leq p[i]$. Ключевая идея состоит в том, чтобы перебирать $i$ и для каждого $i$ (вне зависимости от его простоты) перебирать только нужные множители (простые числа от 2 до $p[i]$).

Для этого нам понадобится поддерживать массив $p$ и дополнительно хранить все встретившиеся нам простые числа.

Приведем реализацию:

 1 vector<int> primes(int n) {
 2     vector<int> p(n + 1, 0);
 3     vector<int> primes; // вектор найденных простых чисел
 4     for (int i = 2; i <= n; ++i) {
 5         if (p[i] == 0) { // i - простое
 6             p[i] = i;
 7             primes.push_back(i);
 8         }
 9         for (int x : primes) {
10             if (x > p[i] || 1ll * x * i > n)
11                 break;
12             p[x * i] = x;
13         }
14     }
15     return p;
16 }

Алгоритм требует в 4 раза больше памяти, чем реализация с vector<char> и в 32 раза больше памяти, чем реализация с vector<bool>. Линейное решето хоть и помогает нам добиться асимптотики $O(n)$, но проигрывает оптимизированному варианту решета Эратосфена за $O(n \cdot \log{\log{n}})$ из-за умножений и еще больших скачков по памяти.

Применение

После предподсчета вектора $p$ мы знаем, какие числа простые (все $x$, для которых $p[x] = x$), а для каждого составного числа знаем его минимальный простой делитель. Нетрудно понять, что вектор $p$ позволяет нам теперь находить факторизацию любого числа от $1$ до $n$ за количество его делителей: возьмем число $x$, поделим его на $p[x]$ (запомнив, что $p[x]$ входит в факторизацию) и будем повторять так до тех пор, пока $x \neq 1$. Так же, заведя еще один массив $h[x] = x / p[x]$, мы можем совсем избавиться от делений при факторизации числа.



Автор конспекта: Егор Гутров

По всем вопросам пишите в telegram @egor_gutrov