E020. Sieve of Eratosthenes с линейным временем работы

Источник: e-maxx.ru/algo, страница PDF 54.

given number

. it is required find все простые в отрезке

. Классический способ решения этой задачи — Sieve of Eratosthenes. Этот Algorithm очень прост, но работает

за время

. Хотя в настоящий момент известно достаточно много Algorithmов, работающих за сублинейное время (т.е. за ), описываемый ниже Algorithm интересен своей простотой — он практически не сложнее классического решета Эратосфена. Кроме того, приводимый здесь Algorithm в качестве "побочного эффекта" фактически вычисляет

факторизацию всех чисел в отрезке

, что может быть полезно во многих практических Applicationsх. Недостатком приводимого Algorithmа является то, что он использует больше памяти, чем классическое

Sieve of Eratosthenes: it is required заводить array из

чисел, в то время как классическому решету Эратосфена

достаточно лишь

бит памяти (что получается в

раза меньше). Таким образом, описываемый Algorithm имеет смысл применять только до чисел порядка , не более. Авторство Algorithmа, по всей видимости, принадлежит Грайсу и Мисра (Gries, Misra, 1978 г. — см. список литературы в конце). (И, собственно говоря, называть данный Algorithm "решетом Эратосфена" некорректно: слишком отличаются

эти два Algorithmа.)

Описание Algorithmа

Наша цель — посчитать для каждого числа

от в отрезке

его minimum простой делитель

. Кроме того, нам поit is required хранить список всех найденных простых чисел — назовём его arrayом .

Изначально все величины

заполним нулями, что означает, что мы пока предполагаем все числа простыми. В ходе работы Algorithmа этот array будет постепенно заполняться.

Будем теперь перебирать текущее number

от

до

. У нас может быть два случая:

●

— это означает, что number

— простое, т.к. для него так и не обнаружилось других делителей.

Следовательно, надо присвоить

и добавить

в конец списка

.

●

— это означает, что текущее number

— составное, и его минимальным простым делителем является

. В обоих случаях дальше начинается процесс расстановки значений в arrayе

: мы будем брать

числа, кратные

, и обновлять у них значение

. Однако наша цель — научиться делать это таким образом, чтобы

в итоге у каждого числа значение

было бы установлено не более одного раза. Утверждается, что для этого можно поступить таким образом. Рассмотрим числа вида:

где последовательность

— это все простые, не превосходящие

(как раз для этого нам понадобилось

хранить список всех простых чисел).

У всех чисел такого вида проставим новое значение

— очевидно, оно будет равно

. Почему такой Algorithm корректен, и почему он работает за линейное время — см. ниже, пока же приведём его реализацию.

Implementation

Решето выполняется до указанного в константе числа

.

const int N = 10000000;

int lp[N+1];

vector<int> pr;

for (int i=2; i<=N; ++i) {

if (lp[i] == 0) {

lp[i] = i;

pr.push_back (i);

}

for (int j=0; j<(int)pr.size() && pr[j]<=lp[i] && i*pr[j]<=N; ++j)

lp[i * pr[j]] = pr[j];

}

Эту реализацию можно немного ускорить, избавившись от вектора

(заменив его на обычный array со счётчиком),

а также избавившись от дублирующегося умножения во вложенном цикле

(для чего результат произведения

надо просто запомнить в какой-либо переменной).

Correctness proof

Докажем корректность Algorithmа, т.е. что он корректно расставляет все значения

, причём каждое из них

будет установлено ровно один раз. Отсюда будет следовать, что Algorithm работает за линейное время — поскольку

все остальные действия Algorithmа, очевидно, работают за

.

Для этого заметим, что у любого числа

единственно представление такого вида:

где

— (как и раньше) minimum простой делитель числа

, а number

не имеет делителей, меньших

, т.е.: Теперь сравним это с тем, что делает наш Algorithm — он фактически для каждого

перебирает все простые, на

которые его можно домножить, т.е. простые до

включительно, чтобы получить числа в указанном

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

него правильное значение

. Это означает корректность Algorithmа и то, что он работает за линейное время.

Running time и требуемая память

Хотя Asymptotic complexity

лучше асимптотики

классического решета Эратосфена, разница между

ними невелика. На практике это означает лишь двукратную разницу в скорости, а оптимизированные варианты решета Эратосфена и вовсе не проигрывают приведённому здесь Algorithmу. given затраты памяти, которые требует этот Algorithm — array чисел

длины

и array всех простых

длины Exampleно

— этот Algorithm кажется уступающим классическому решету по всем статьям.

Однако спасает его то, что array

, вычисляемый этим Algorithmом, позволяет искать факторизацию любого числа

в отрезке

за время порядка размера этой факторизации. Более того, ценой ещё одного дополнительного arrayа можно сделать, чтобы в этой факторизации не требовались операции деления. Знание факторизации всех чисел — очень полезная информация для некоторых задач, и этот Algorithm является одним из немногих, которые позволяют искать её за линейное время.

References

● David Gries, Jayadev Misra. A Linear Sieve Algorithm for Finding Prime Numbers [1978]