MAXimal | |
добавлено: 6 Sep 2011 1:03 Содержание [скрыть] Решето Эратосфена с линейным временем работыДано число Классический способ решения этой задачи — решето Эратосфена. Этот алгоритм очень прост, но работает за время Хотя в настоящий момент известно достаточно много алгоритмов, работающих за сублинейное время (т.е. за Кроме того, приводимый здесь алгоритм в качестве "побочного эффекта" фактически вычисляет факторизацию всех чисел в отрезке Недостатком приводимого алгоритма является то, что он использует больше памяти, чем классическое решето Эратосфена: требуется заводить массив из Таким образом, описываемый алгоритм имеет смысл применять только до чисел порядка Авторство алгоритма, по всей видимости, принадлежит Грайсу и Мисра (Gries, Misra, 1978 г. — см. список литературы в конце). (И, собственно говоря, называть данный алгоритм "решетом Эратосфена" некорректно: слишком отличаются эти два алгоритма.) Описание алгоритмаНаша цель — посчитать для каждого числа Кроме того, нам потребуется хранить список всех найденных простых чисел — назовём его массивом Изначально все величины Будем теперь перебирать текущее число
В обоих случаях дальше начинается процесс расстановки значений в массиве Утверждается, что для этого можно поступить таким образом. Рассмотрим числа вида: где последовательность У всех чисел такого вида проставим новое значение Почему такой алгоритм корректен, и почему он работает за линейное время — см. ниже, пока же приведём его реализацию. РеализацияРешето выполняется до указанного в константе числа 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]; } Эту реализацию можно немного ускорить, избавившись от вектора Доказательство корректностиДокажем корректность алгоритма, т.е. что он корректно расставляет все значения Для этого заметим, что у любого числа где Теперь сравним это с тем, что делает наш алгоритм — он фактически для каждого Следовательно, алгоритм действительно пройдёт по каждому составному числу ровно один раз, поставив у него правильное значение Это означает корректность алгоритма и то, что он работает за линейное время. Время работы и требуемая памятьХотя асимптотика Учитывая затраты памяти, которые требует этот алгоритм — массив чисел Однако спасает его то, что массив Знание факторизации всех чисел — очень полезная информация для некоторых задач, и этот алгоритм является одним из немногих, которые позволяют искать её за линейное время. Литература
|