Почему Сито Эратосфена более эффективно, чем простой "тупой" алгоритм?

Если вам нужно сгенерировать простые числа от 1 до N, "тупой" способ сделать это - перебрать все числа от 2 до N и проверить, не делятся ли числа на любое число, найденное до сих пор, меньше квадратного корня из числа, о котором идет речь.

Как я вижу, сито Эратосфена делает то же самое, кроме другого пути - когда он находит простое N, он отмечает все числа, кратные N.

Но отметим ли вы, что X, когда вы находите N, или проверяете, является ли X делимым на N, фундаментальная сложность, big-O остается неизменной. Вы по-прежнему выполняете одну операцию с постоянным временем на пару с числом-первыми. Фактически, немой алгоритм прерывается, как только он находит премьер, но сито Эратосфена отмечает каждое число несколько раз - один раз для каждого штриха он делится на. Это минимум вдвое больше операций для каждого числа, кроме простых.

Неужели я что-то не понимаю?

Ответы

Ответ 1

В алгоритме пробного деления большая часть работы, которая может потребоваться для определения того, является ли число n простым, - это проверка делимости на простые числа до sqrt(n).

Тот худший случай встречается, когда n является простым или произведением двух простых чисел почти одинакового размера (включая квадраты простых чисел). Если n имеет более двух простых коэффициентов или два простых коэффициента очень разных размеров, по крайней мере один из них намного меньше, чем sqrt(n), поэтому даже накопленная работа, необходимая для всех этих чисел (которые составляют подавляющее большинство все числа до n, при достаточно больших n) относительно незначителен, я проигнорирую это и буду работать с вымыслом о том, что составные числа определяются без какой-либо работы (продукты двух приблизительно равных простых чисел немногочисленны, поэтому, хотя индивидуально они стоят столько же, сколько простота такого же размера, в целом это незначительная работа).

Итак, сколько работы выполняется при тестировании простых чисел до n?

По теореме о простом числе число простых чисел <= n (при n достаточно велико), около n/log n (it n/log n + lower order terms). Обратно, это означает, что k -е простое (для k не слишком мало) около k*log k (+ младшие члены).

Следовательно, для тестирования k-го шага требуется пробное деление на pi(sqrt(p_k)), приблизительно 2*sqrt(k/log k), простые числа. Суммируя, что для k <= pi(N) ~ N/log N получается примерно 4/3*N^(3/2)/(log N)^2 делений в целом. Поэтому, игнорируя композиты, мы обнаружили, что поиск простых чисел до n путем пробного деления (с использованием только простых чисел) составляет Omega(N^1.5 / (log N)^2). Более тщательный анализ композитов показывает, что он Theta(N^1.5 / (log N)^2). Использование колеса уменьшает постоянные факторы, но не меняет сложность.

В сите, с другой стороны, каждый композит сбрасывается как кратный по меньшей мере одному простому. В зависимости от того, начинаете ли вы переходить на 2*p или в p*p, композит сбрасывается столько раз, сколько он имеет различные простые коэффициенты или различные простые коэффициенты <= sqrt(n). Поскольку любое число имеет не более одного простого множителя, превышающего sqrt(n), разница не столь велика, она не влияет на сложность, но существует множество чисел только с двумя основными факторами (или тремя с одним большим, чем sqrt(n)), таким образом, он делает заметную разницу в времени выполнения. Во всяком случае, число n > 0 имеет только несколько различных простых факторов, тривиальная оценка показывает, что число различных простых факторов ограничено lg n (логарифмом базы-2), поэтому верхняя граница для количества пересечений sieve does N*lg N.

Не подсчитывая, насколько часто каждый композит сбрасывается, но сколько кратных каждого штриха сбрасывается, как уже сделал IVlad, легко найти, что количество переходов - фактически Theta(N*log log N). Опять же, использование колеса не изменяет сложность, а уменьшает постоянные факторы. Однако здесь это имеет большее влияние, чем для пробного деления, поэтому необходимо, по крайней мере, пропустить выравнивание (кроме сокращения работы, оно также уменьшает размер хранилища, поэтому улучшает локальность кеша).

Таким образом, даже не считая этого деления более дорогостоящим, чем добавление и умножение, мы видим, что количество операций, которое требует сит, намного меньше числа операций, требуемых пробным делением (если предел не слишком мал).

Резюмируя:
Судебное деление делает бесполезную работу делением простых чисел, сито делает бесполезную работу, неоднократно пересекая композиты. Есть относительно мало простых чисел, но много композитов, поэтому у вас может возникнуть соблазн подумать о том, что отходы, связанные с разделением, меньше работают. Но: Композиты имеют только несколько различных простых факторов, тогда как существует множество простых чисел ниже sqrt(p).

Ответ 2

В наивном методе вы выполняете операции O(sqrt(num)) для каждого номера num, который вы проверяете на простоту. Ths O(n*sqrt(n)) total.

В ситовом методе для каждого немаркированного числа от 1 до n вы выполняете операции n / 2 при маркировке кратных 2, n / 3 при маркировке тегов 3, n / 5 при маркировке 5 и т.д. Это n*(1/2 + 1/3 + 1/5 + 1/7 + ...), который равен O(n log log n). См. здесь для этого результата.

Таким образом, асимптотическая сложность не то же самое, как вы сказали. Даже наивное сито будет очень быстро избивать наивный метод простого поколения. Оптимизированные версии сита могут быть намного быстрее, но большой-ох остается неизменным.

Эти два не эквивалентны, как вы говорите. Для каждого числа вы проверите делимость на те же простые числа 2, 3, 5, 7, ... в алгоритме наивного простого генерации. По мере того, как вы продвигаетесь, вы проверяете делимость на одну и ту же серию чисел (и вы продолжаете проверять все больше и больше по мере приближения к вашему n). Для сита вы все меньше и больше проверяете, когда приближаетесь к n. Сначала вы проверяете приращения 2, затем 3, затем 5 и так далее. Это ударит n и остановится намного быстрее.

Ответ 3

Поскольку с помощью метода сита вы перестаете отмечать мультипликации запущенных простых чисел, когда пробег пробега достигает квадратного корня N.

Скажем, вы хотите найти все простые числа менее миллиона.

Сначала вы установите массив

for i = 2 to 1000000
  primetest[i] = true

Затем вы повторяете

for j=2 to 1000         <--- 1000 is the square root of 10000000
  if primetest[j]                                    <--- if j is prime
    ---mark all multiples of j (except j itself) as "not a prime"
    for k = j^2 to 1000000 step j
      primetest[k] = false

Вам не нужно проверять j после 1000, потому что j * j будет больше миллиона. И вы начинаете с j * j (вам не нужно отмечать кратные j меньше j ^ 2, потому что они уже отмечены как кратные ранее найденным, меньшим числам)

Итак, в конце вы сделали цикл 1000 раз, а часть if - только для тех j, которые являются простыми.

Вторая причина заключается в том, что с ситом вы делаете только умножение, а не деление. Если вы делаете это с умом, вы делаете только добавление, даже не умножение.

И деление имеет большую сложность, чем добавление. Обычный способ деления имеет сложность O(n^2), а добавление имеет O(n).

Ответ 5

Первое отличие состоит в том, что деление намного дороже, чем добавление. Даже если каждое число "отмечено" несколько раз, оно тривиально по сравнению с огромным количеством делений, необходимых для "немого" алгоритма.

Ответ 6

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