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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Решето́ Эратосфе́на — алгоритм нахождения всех простых чисел до некоторого целого числа n, который приписывают древнегреческому математику Эратосфену Киренскому[1]. Как и во многих случаях, здесь название алгоритма говорит о принципе его работы, то есть решето подразумевает фильтрацию, в данном случае фильтрацию всех чисел за исключением простых. По мере прохождения списка нужные числа остаются, а ненужные (они называются составными) исключаются.

История[править | править код]

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

Алгоритм[править | править код]

Анимация шагов алгоритма Эратосфена для нахождения простых чисел до 120

Для нахождения всех простых чисел не больше заданного числа n, следуя методу Эратосфена, нужно выполнить следующие шаги:

  1. Выписать подряд все целые числа от двух до n (2, 3, 4, …, n).
  2. Пусть переменная p изначально равна двум — первому простому числу.
  3. Зачеркнуть в списке числа от 2p до n считая шагами по p (это будут числа кратные p: 2p, 3p, 4p, …).
  4. Найти первое незачёркнутое число в списке, большее чем p, и присвоить значению переменной p это число.
  5. Повторять шаги 3 и 4, пока возможно.

Теперь все незачёркнутые числа в списке — это все простые числа от 2 до n.

На практике, алгоритм можно улучшить следующим образом. На шаге № 3 числа можно зачеркивать начиная сразу с числа p2, потому что все составные числа меньше него уже будут зачеркнуты к этому времени. И, соответственно, останавливать алгоритм можно, когда p2 станет больше, чем n.[2] Также, все простые числа (кроме 2) — нечётные числа, и поэтому для них можно считать шагами по 2p, начиная с p2.

Пример для n = 30[править | править код]

Запишем натуральные числа начиная от 2 до 30 в ряд:

2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

Первое число в списке, 2 — простое. Пройдём по ряду чисел, зачёркивая все числа кратные 2 (то есть каждое второе, начиная с 22 = 4):

2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

Следующее незачеркнутое число, 3 — простое. Пройдём по ряду чисел, зачёркивая все числа кратные 3 (то есть каждое третье, начиная с 32 = 9):

2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

Следующее незачеркнутое число, 5 — простое. Пройдём по ряду чисел, зачёркивая все числа кратные 5 (то есть каждое пятое, начиная с 52 = 25):

2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

Следующее незачеркнутое число — 7. Его квадрат, 49 — больше 30-ти, поэтому на этом работа завершена. Все составные числа уже зачеркнуты:

2  3     5     7           11    13          17    19          23                29

Псевдокод[править | править код]

Оптимизированная реализация (начинающаяся с квадратов) на псевдокоде[3][4]:

Вход: натуральное число n

Пусть Aбулевый массив, индексируемый числами от 2 до n, 
изначально заполненный значениями true.

 для i := 2, 3, 4, ..., пока i2n:
  если A[i] = true:
    для j := i2, i2 + i, i2 + 2i, ..., пока jn:
      A[j] := false

Выход: числа i, для которых A[i] = true.

Сложность алгоритма[править | править код]

Сложность алгоритма составляет операций при составлении таблицы простых чисел до [5].

Доказательство сложности[править | править код]

При выбранном для каждого простого будет выполняться внутренний цикл, который совершит действий. Следовательно, нужно оценить следующую величину:

Так как количество простых чисел, меньших либо равных , оценивается как , и, как следствие, -е простое число примерно равно , то сумму можно преобразовать:

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

В итоге получается для изначальной суммы:

Более строгое доказательство (и дающее более точную оценку с точностью до константных множителей) можно найти в книге Hardy и Wright «An Introduction to the Theory of Numbers»[6].

Модификации метода[править | править код]

Неограниченный, постепенный вариант[править | править код]

В этом варианте простые числа вычисляются последовательно, без ограничения сверху,[7] как числа находящиеся в промежутках между составными числами, которые вычисляются для каждого простого числа p, начиная с его квадрата, с шагом в p (или для нечетных простых чисел 2p)[2]. Может быть представлен символически в парадигме потоков данных как

 primes = [2..] \ [[, +p..] for p in primes]

используя нотацию абстракции списков, где \ обозначает разницу между арифметическими прогрессиями.

Первое простое число 2 (среди возрастающих положительных целых чисел) заранее известно, поэтому в этом самореферентном определении нет порочного круга.

Псевдокод поэтапного отсеивания, в неэффективной, для простоты, реализации (ср. с нижеследующими вариантами):

 primes = sieve [2..] where
          sieve [p, ...xs...] = [p, ...sieve (xs \ [p*n for n in [p..]])...]

Перебор делителей[править | править код]

Решето Эратосфена часто путают с алгоритмами, которые поэтапно отфильтровывают составные числа, тестируя каждое из чисел-кандидатов на делимость используя по одному простому числу на каждом этапе.[8]

Широко известный функциональный код Дэвида Тёрнера 1975г.[9] часто принимают за решето Эратосфена,[8] но на самом деле[7] это неоптимальный вариант с перебором делителей (в оптимальном варианте не используются делители, большие квадратного корня тестируемого числа). В псевдокоде,

 primes = sieve [2..] where
          sieve [p, ...xs...] = [p, ...sieve [x in xs if not (x%p == 0)]...]

Сегментированное решето[править | править код]

Как отмечает Соренсон, главной проблемой реализации решета Эратосфена на вычислительных машинах является не количество выполняемых операций, а требования по объёму занимаемой памяти.[4] При больших значениях n, диапазон простых чисел может превысить доступную память; хуже того, даже при сравнительно небольших n использование кэша памяти далеко от оптимального, так как алгоритм, проходя по всему массиву, нарушает принцип локализованности ссылок.

Для решения представленной проблемы используется сегментированное решето, в котором за итерацию просеивается только часть диапазона простых чисел.[10] Данный метод известен с 1970-х годов и работает следующим образом:[4][11]

  1. Разделяем диапазон от 2 до n на отрезки (сегменты) некоторой длины Δ ≤ n.
  2. Находим все простые числа в первом отрезке, используя обычное решето.
  3. Каждый из последующих отрезков оканчивается на некотором числе m. Находим все простые числа в отрезке следующим образом:
    1. Создаем булевый массив размера Δ
    2. Для каждого простого числа pm из уже найденных, отмечаем в массиве как "непростые" все числа кратные p, перебирая числа с шагом в p, начиная с наименьшего кратного p числа в данном отрезке.

Если число Δ выбрано равным n, то сложность алгоритма по памяти оценивается как O(n), а временная сложность остаётся такой же, что и у обычного решета Эратосфена.

Для случаев, когда n настолько велико, что все просеиваемые простые числа меньшие n не могут уместиться в памяти, как того требует алгоритм сегментированного сита, используют более медленные, но с гораздо меньшими требованиями по памяти алгоритмы, например решето Соренсона.[12]

Решето Эйлера[править | править код]

Доказательство тождества Эйлера для дзета-функции Римана содержит механизм отсеивания составных чисел подобный решету Эратосфена, но так, что каждое составное число удаляется из списка только один раз. Схожее решето описано в Gries & Misra 1978г. как решето с линейным временем работы (см. ниже).

Составляется исходный список начиная с числа 2. На каждом этапе алгоритма первый номер в списке берется как следующее простое число, результаты произведения которого на каждое число в списке помечаются для последующего удаления. После этого из списка убирают первое число и все помеченные числа, и процесс повторяется вновь:

[2] (3) 5  7  9 11  13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79  ...
[3]    (5) 7    11  13    17 19    23 25    29 31    35 37    41 43    47 49    53 55    59 61    65 67    71 73    77 79  ...
[4]       (7)   11  13    17 19    23       29 31       37    41 43    47 49    53       59 61       67    71 73    77 79  ...
[5]            (11) 13    17 19    23       29 31       37    41 43    47       53       59 61       67    71 73       79  ...
[...] 

Здесь показан пример начиная с нечетных чисел, после первого этапа алгоритма. Таким образом, после k-го этапа рабочий список содержит только числа взаимно простые с первыми k простыми числами (то есть числа не кратные ни одному из первых k простых чисел), и начинается с (k+1)-го простого числа. Все числа в списке, меньшие квадрата его первого числа, являются простыми.

В псевдокоде,

 primes = sieve [2..] where
          sieve [p, ...xs...] = [p, ...sieve (xs \ [p*n for n in [p, ...xs...]])...]

Решето только по нечётным числам[править | править код]

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

Это можно обобщить на числа взаимно простые не только с 2 (то есть нечетные числа), но и с 3, 5, и т. д.

Уменьшение объёма потребляемой памяти[править | править код]

Алгоритм Эратосфена фактически оперирует с битами памяти. Следовательно, можно существенно сэкономить потребление памяти, храня переменных булевского типа не как байт, а как бит, то есть байт памяти.

Такой подход — «битовое сжатие» — усложняет оперирование этими битами. Любое чтение или запись бита будут представлять собой несколько арифметических операций. Но с другой стороны существенно улучшается компактность в памяти. Бо́льшие интервалы умещаются в кэш-память которая работает гораздо быстрее обычной так что при работе по-сегментно общая скорость увеличивается.

Решето Эратосфена с линейным временем работы[править | править код]

Этот алгоритм обнаруживает для каждого числа i в отрезке [2...n] его минимальный простой делитель lp[i].

Также поддерживается список всех простых чисел — массив pr[], поначалу пустой. В ходе работы алгоритма этот массив будет постепенно заполняться.

Изначально все величины lp[i] заполним нулями.

Дальше следует перебрать текущее число i от 2 до n. Здесь может быть два случая:

  •   lp[i] = 0: это означает, что число i — простое, так как для него так и не обнаружилось других делителей.

Следовательно, надо присвоить lp[i] = i и добавить i в конец списка pr[].

  •   lp[i] ≠ 0: это означает, что текущее число i — составное, и его минимальным простым делителем является lp[i].

В обоих случаях дальше начинается процесс расстановки значений в массиве lp[i]: следует брать числа, кратные i, и обновлять у них значение lp[]. Однако основная цель — научиться делать это таким образом, чтобы в итоге у каждого числа значение lp[] было бы установлено не более одного раза.

Утверждается, что для этого можно поступить таким образом. Рассматриваются числа вида x = p ⋅ i, где p последовательно равно всем простым числам не превосходящим lp[i] (как раз для этого понадобилось хранить список всех простых чисел).

У всех чисел такого вида проставим новое значение lp[x] — оно должно быть равно p[13].

Псевдокод[править | править код]

 Вход: натуральное число n

Пусть pr - целочисленный массив, поначалу пустой;
      lp - целочисленный массив, индексируемый от 2 до n, заполненный нулями

 для i := 2, 3, 4, ..., до n: 
   если lp[i] = 0:
       lp[i] := i
       pr[] += {i}
   для p из pr пока plp[i] и p*in:
       lp[p*i] := p

Выход: все числа в массиве pr.

Сложность алгоритма на практике[править | править код]

Решето Эратосфена является популярным способом оценки производительности компьютера.[14] Как видно из вышеизложенного доказательства сложности алгоритма, игнорируя все константы и избавляясь от слагаемых стремящихся к нулю, при n стремящемся к бесконечности, временная сложность вычисления всех простых чисел меньше n равна O(n log log n). Однако алгоритм имеет экспоненциальную временную сложность в отношении размера входных данных, что делает его псевдополиномиальным алгоритмом. Памяти же для базового алгоритма требуется O(n).

Стандартная реализованная сегментированная версия имеет ту же операционную сложность O(n log log n), что и несегментированная версия, но уменьшает потребность в используемой памяти до крайне минимального размера сегмента, который равен O(√n/log n). Также существует очень редко встречающееся на практике сегментированное решето Эратосфена с базовой оптимизацией. Оно строится за O(n) операций и занимает O(√nlog log n/log n) бит в памяти.[15][16][17]

Для демонстрации того, что описанная выше аппроксимация по операционной сложности является не очень точной даже для максимальных практических диапазонов, ниже приведена таблица с расчетным количеством операций на долю диапазона, округленного до четырех знаков после запятой, соотношение коэффициента десятикратного изменения в диапазоне, рассчитанного по данной оценке, и коэффициентом, основывающимся на оценке log log n для различных диапазонов и кольцевых факторизаций (в комбинированной колонке используется весьма популярный предварительный отбор по максимальной степени кольцевой факторизации, но только 2/3/5/7 кольцо при условии полной факторизации трудно эффективно реализовать для сегментированной версии сита):

n без факторизации некольцевая факторизация 2/3/5 кольцо 2/3/5/7 кольцо комбинированное кольцо 2/3/5/7/11/13/17/19 кольцо
106 2.122 1.102 1.075 0.811 1.137 1.075 0.2903 1.22 1.075 0.2162 1.261 1.075 0.1524 1.416 1.075 0.114 1.416 1.075
107 2.2863 1.077 1.059 0.8932 1.101 1.059 0.3341 1.151 1.059 0.2537 1.174 1.059 0.1899 1.246 1.059 0.1421 1.246 1.059
108 2.4276 1.062 1.048 0.9638 1.079 1.048 0.3718 1.113 1.048 0.286 1.127 1.048 0.2222 1.17 1.048 0.1662 1.17 1.048
109 2.5514 1.051 1.04 1.0257 1.064 1.04 0.4048 1.089 1.04 0.3143 1.099 1.04 0.2505 1.127 1.04 0.1874 1.127 1.04
1010 2.6615 1.043 1.035 1.0808 1.054 1.035 0.4342 1.073 1.035 0.3395 1.08 1.035 0.2757 1.101 1.035 0.2063 1.101 1.035
1011 2.7608 1.037 1.03 1.1304 1.046 1.03 0.4607 1.061 1.03 0.3622 1.067 1.03 0.2984 1.082 1.03 0.2232 1.082 1.03
1012 2.8511 1.033 1.027 1.1755 1.04 1.027 0.4847 1.052 1.027 0.3828 1.057 1.027 0.319 1.069 1.027 0.2387 1.069 1.027
1013 2.9339 1.029 1.024 1.217 1.035 1.024 0.5068 1.046 1.024 0.4018 1.049 1.024 0.3379 1.059 1.024 0.2528 1.059 1.024
1014 3.0104 1.026 1.022 1.2552 1.031 1.022 0.5272 1.04 1.022 0.4193 1.044 1.022 0.3554 1.052 1.022 0.2659 1.052 1.022
1015 3.0815 1.024 1.02 1.2907 1.028 1.02 0.5462 1.036 1.02 0.4355 1.039 1.02 0.3717 1.046 1.02 0.2781 1.046 1.02
1016 3.1478 1.022 1.018 1.3239 1.026 1.018 0.5639 1.032 1.018 0.4507 1.035 1.018 0.3868 1.041 1.018 0.2894 1.041 1.018

Вышеприведенное показывает, что оценка log log n не очень точна даже для максимальных практических диапазонов таких как 1016. Ознакомившись с вышеописанным доказательством сложности, нетрудно понять откуда взялось такое расхождение. Дело в том, что в пределах данного практического диапазона просеивания существенное влияние оказывают постоянные смещения. Таким образом очень медленно растущий член log log n не становится достаточно большим, чтобы константами можно было справедливо пренебречь, до тех пор пока n не приблизится к бесконечности, что естественно выходит за границы любого прикладного диапазона просеивания. Данный факт показывает, что для актуальных на сегодняшний день входных данных производительность сита Эратосфена намного лучше, чем следовало ожидать, используя только асимптотические оценки временной сложности. Но также это свидетельствует, что наклон производительности круче, чем прогнозировалось, поскольку с увеличением числа n вклад констант смещения становится немного менее значительным.

Следует также отметить, что коэффициент работы, рассчитанный выше, должен быть меньше чем 0.2587, чтобы решето Эратосфена работало быстрее, чем часто с ним сравниваемое решето Аткина. Сказанное справедливо при условии того, что операции занимают примерно одно и тоже время в циклах центрального процессора, а это является разумным предположением для одного алгоритма, работающего с огромным битовым массивом. Используя это предположение, получаем, что сито Аткина быстрее чем максимально факторизованное решето Эратосфена для n свыше 10 13 , но при таких диапазонах просеивания потребуется приблизительно четверть терабайта (около 250 гигабайт) оперативной памяти, даже если была использована "битовая упаковка". Однако анализ для сегментированных версий алгоритмов (см. ниже) показывает, что предположение о сохранении равенства во времени, затрачиваемом на одну операции, между двумя алгоритмами не выполняется при сегментации. В свою очередь это приводит к тому, что решето Аткина работает медленнее, чем сегментированное решето Эратосфена с увеличением диапазона просеивания, за счёт уменьшения времени на операцию для второго.

Использование нотации O большого также не является правильным способом сравнения практических характеристик даже для вариаций сита Эратосфена, поскольку данная нотация игнорирует константы и смещения, которые могут быть очень значительными для прикладных диапазонов. Например, одна из вариаций сита Эратосфена известная как решето Притчарда[15][16][17] имеет производительность O(n), но её базовая реализация требует либо алгоритма «одного большого массива», который ограничивает его диапазон использования до объема доступной памяти, либо он должен быть сегментирован страницей для уменьшения использования памяти. Когда реализован сегментированный алгоритм для сохранения памяти, базовый алгоритм по-прежнему требует наличия O(n/log n) бит памяти (гораздо больше, чем требование базового сеточного разделения решетки Эратосфена с использованием O(√n/log n) бит памяти). Работа Притчарда уменьшила требования к памяти до предела, как описано выше в таблице, но платой за данное улучшение по памяти является довольно большой постоянный коэффициент (около трёх), применяющийся примерно до трёх четвертей диапазона сита из-за сложных вычислений.

См. также[править | править код]

Примечания[править | править код]

  1. Никомах Герасский, Введение в арифметику, I, 13. [1]
  2. 1 2 Horsley, Rev. Samuel, F. R. S., "Κόσκινον Ερατοσθένους or, The Sieve of Eratosthenes. Being an Account of His Method of Finding All the Prime Numbers, " Philosophical Transactions (1683—1775), Vol. 62. (1772), pp. 327—347.
  3. Algorithms in C++. — Addison-Wesley, 1992. — ISBN 0-201-51059-6., p. 16.
  4. 1 2 3 Jonathan Sorenson, An Introduction to Prime Number Sieves, Computer Sciences Technical Report #909, Department of Computer Sciences University of Wisconsin-Madison, January 2 1990 (the use of optimization of starting from squares, and thus using only the numbers whose square is below the upper limit, is shown).
  5. Волшебное решето Эратосфена
  6. Hardy and Wright "An Introduction to the Theory of Numbers, p. 349
  7. 1 2 O'Neill, Melissa E., "The Genuine Sieve of Eratosthenes", Journal of Functional Programming, Published online by Cambridge University Press 9 October 2008 DOI:10.1017/S0956796808007004.
  8. 1 2 Colin Runciman, «FUNCTIONAL PEARL: Lazy wheel sieves and spirals of primes», Journal of Functional Programming, Volume 7 Issue 2, March 1997; также здесь.
  9. Turner, David A. SASL language manual. Tech. rept. CS/75/1. Department of Computational Science, University of St. Andrews 1975. (sieve (p:xs) = p:sieve [x | x <- xs, rem x p > 0]; primes = sieve [2..])
  10. Crandall & Pomerance, Prime Numbers: A Computational Perspective, second edition, Springer: 2005, pp. 121–24.
  11. (1977) «The segmented sieve of Eratosthenes and primes in arithmetic progressions to 1012». BIT 17 (2): 121–127. DOI:10.1007/BF01932283.
  12. J. Sorenson, The pseudosquares prime sieve, Proceedings of the 7th International Symposium on Algorithmic Number Theory. (ANTS-VII, 2006).
  13. David Gries, Jayadev Misra. A Linear Sieve Algorithm for Finding Prime Numbers [1978]
  14. Peng, T. A.. One Million Primes Through the Sieve, BYTE (Fall 1985), стр. 243–244. Проверено 19 марта 2016.
  15. 1 2 Paul Pritchard, A sublinear additive sieve for finding prime numbers, Communications of the ACM 24 (1981), 18–23.
  16. 1 2 Paul Pritchard, Explaining the wheel sieve, Acta Informatica 17 (1982), 477–485.
  17. 1 2 Paul Pritchard, Fast compact prime number sieves (among others), Journal of Algorithms 4 (1983), 332–344.

Литература[править | править код]

Ссылки[править | править код]