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

Question

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

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

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

Я что-то здесь неправильно понимаю?

Answer 1

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

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

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

По теореме о простых числах число простых чисел <= n равно (для достаточно большого n) примерно n/log n (это 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), разница не так велика, это не влияет на сложность, но существует множество чисел, имеющих только два простых множителя (или три с одним, превышающим * 1041). *), таким образом, это делает заметную разницу во времени выполнения. В любом случае, число n > 0 имеет только несколько различных простых факторов, тривиальная оценка показывает, что число различных простых факторов ограничено lg n (логарифм с основанием 2), поэтому верхняя граница для числа вычетов сито это N*lg N.

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

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

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

Answer 2

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

В методе просеивания для каждого немаркированного числа от 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 и остановится намного быстрее.

Answer 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).

Answer 4

Объяснено в этой статье: http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf

Я думаю, что это вполне читабельно, даже без знания Haskell.

Answer 5

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

Answer 6

http://en.wikipedia.org/wiki/Prime_number#Number_of_prime_numbers_below_a_given_number

• «тупой» алгоритм работает i/log(i) ~= N/log(N) для каждого простого числа
• реальный алгоритм работает N/i ~= 1 для каждого простого числа

Умножьте примерно на N/log(N) простых чисел.

Answer 7

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