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

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

История


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

Алгоритм


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

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

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

Сложностьалгоритма


 Сложность алгоритма составляет O(nlog(logn)) операций присоставлении таблицы простых чисел до n.

Доказательствосложности


 При выбранном nN для каждого простогоpP:pn будет выполняться внутренний цикл,который совершит np действий. Следовательно, нужно оценитьследующую величину:
pP:pnnp=npP:pn1p
 Так как количество простых чисел, меньших либо равных n, оцениваетсякак nlnn, и, как следствие, k-е простое число примерноравно klnk, то сумму можно преобразовать:
pP:pn1p12+k=2nlnn1klnk
 Здесь из суммы выделено слагаемое для первого простого числа, чтобыизбежать деления на нуль. Теперь следует оценить эту сумму интегралом:
12+k=2nlnn1klnk2nlnn1klnkdk=lnlnk|2nlnn=lnlnnlnnlnln2=ln(lnnlnlnn)lnln2lnlnn
 В итоге получается для изначальной суммы:
pP:pnnpnlnlnn+o(n)
 Более строгое доказательство (и дающее более точную оценку с точностьюдо константных множителей) можно найти в книге Hardy и Wright «AnIntroduction to the Theory of Numbers».

Псевдокод


 Оптимизированная реализация (начинающаяся с квадратов) на псевдокоде:
\textttВход\texttt: натуральное число \textttn\\\\\textttПусть \textttA\texttt — булевый массив, индексируемый числами от 2 до \textttn\texttt, \\\textttизначально заполненный значениями \texttttrue\texttt.\\\\\texttt \textttдля\texttt \texttti\texttt := 2, 3, 4, ..., \textttпока\texttt \texttti\texttt2\texttt ≤ \textttn\texttt:\\\texttt  \textttесли\texttt \textttA\texttt[\texttti\texttt] = \texttttrue\texttt:\\\texttt    \textttдля\texttt \textttj\texttt := \texttti\texttt2\texttt, \texttti\texttt2\texttt + \texttti\texttt, \texttti\texttt2\texttt + 2\texttti\texttt, ..., \textttпока\texttt \textttj\texttt ≤ \textttn\texttt:\\\texttt      \textttA\texttt[\textttj\texttt] := \textttfalse\\\\\textttВыход\texttt: числа \texttti\texttt, для которых \textttA\texttt[\texttti\texttt] = \texttttrue\texttt.
 == Пример для n = 30 == Запишем натуральные числа начиная от до в ряд:
 \texttt2  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
 Первое число в списке,  — простое. Пройдём по ряду чисел, зачёркиваявсе числа кратные (то есть каждое второе, начиная с ):
 \texttt2  3 \texttt 4 \texttt 5 \texttt 6 \texttt 7 \texttt 8 \texttt 9  \texttt10\texttt 11 \texttt12\texttt 13 \texttt14\texttt 15 \texttt16\texttt 17 \texttt18\texttt 19 \texttt20\texttt 21 \texttt22\texttt 23 \texttt24\texttt 25 \texttt26\texttt 27 \texttt28\texttt 29 \texttt30
 Следующее незачеркнутое число,  — простое. Пройдём по ряду чисел,зачёркивая все числа кратные (то есть каждое третье, начиная с ):
 \texttt2  3 \texttt 4 \texttt 5 \texttt 6 \texttt 7 \texttt 8 \texttt 9 \texttt 10\texttt 11 \texttt12\texttt 13 \texttt14 \texttt15 \texttt16\texttt 17 \texttt18\texttt 19 \texttt20 \texttt21 \texttt22\texttt 23 \texttt24\texttt 25 \texttt26 \texttt27 \texttt28\texttt 29 \texttt30
 Следующее незачеркнутое число,  — простое. Пройдём по ряду чисел,зачёркивая все числа кратные 5 (то есть каждое пятое, начиная с ).И т. д.
 \texttt2  3 \texttt 4 \texttt 5 \texttt 6 \texttt 7 \texttt 8 \texttt 9 \texttt 10\texttt 11 \texttt12\texttt 13 \texttt14 \texttt15 \texttt16\texttt 17 \texttt18\texttt 19 \texttt20 \texttt21 \texttt22\texttt 23 \texttt24 \texttt25 \texttt26 \texttt27 \texttt28\texttt 29 \texttt30
 Следующее незачеркнутое число — . Его квадрат, — больше -ти, поэтомуна этом работа завершена. Все составные числа уже зачеркнуты:
 \texttt2  3     5     7           11    13          17    19          23                29

Модификацииметода


Неограниченный, постепенныйвариант


 В этом варианте простые числа вычисляются последовательно, безограничения сверху, как числа находящиеся в промежутках между составнымичислами, которые вычисляются для каждого простого числа , начиная с егоквадрата, с шагом в (или для нечетных простых чисел ). Может бытьпредставлен символически в парадигме потоков данных как
 \texttt \textttprimes \texttt=\texttt[\texttt2\texttt..] \texttt\{\textttp²\texttt,\textttp²\texttt+\textttp\texttt..] \textttfor\textttp \textttin \textttprimes\texttt]
 используя нотацию абстракции списков, где \texttt\{обозначает разницу между арифметическими прогрессиями.
 Первое простое число (среди возрастающих положительных целых чисел)заранее известно, поэтому в этом самореферентном определении нетпорочного круга.

Переборделителей


 Решето Эратосфена часто путают с алгоритмами, которые отфильтровывают иззаданного интервала составные числа, тестируя каждое из чисел-кандидатовс помощью перебора делителей.
 Широко известный функциональный код Дэвида Тёрнера 1975 года частопринимают за решето Эратосфена, но на самом деле это далёкий отоптимального вариант с перебором делителей.

РешетоЭйлера


 Решето Эйлера это вариант решета Эратосфена, в котором каждое составноечисло удаляется из списка только один раз.
 Составляется исходный список начиная с числа . На каждом этапе алгоритмапервый номер в списке берется как следующее простое число, иопределяются его произведения на каждое число в списке которыемаркируются для последуюшего удаления. После этого из списка убираютпервое число и все помеченные числа, и процесс повторяется вновь:
 \\\texttt[2] (3) 5  7 \texttt 9\texttt 11  13 \texttt15\texttt 17 19 \texttt21\texttt 23 25 \texttt27\texttt 29 31 \texttt33\texttt 35 37 \texttt39\texttt 41 43 \texttt45\texttt 47 49 \texttt51\texttt 53 55 \texttt57\texttt 59 61 \texttt63\texttt 65 67 \texttt69\texttt 71 73 \texttt75\texttt 77 79  ...\\\texttt[3]    (5) 7    11  13    17 19    23 \texttt25\texttt    29 31    \texttt35\texttt 37    41 43    47 49    53 \texttt55\texttt    59 61    \texttt65\texttt 67    71 73    77 79  ...\\\texttt[4]       (7)   11  13    17 19    23       29 31       37    41 43    47 \texttt49\texttt    53       59 61       67    71 73    \texttt77\texttt 79  ...\\\texttt[5]            (11) 13    17 19    23       29 31       37    41 43    47       53       59 61       67    71 73       79  ...\\\texttt[...]\\
 Здесь показан пример начиная с нечетных чисел, после первого этапаалгоритма. Таким образом, после -го этапа рабочий список содержит толькочисла взаимно простые с первыми простыми числами (то есть числа некратные ни одному из первых простых чисел), и начинается с -го простогочисла. Все числа в списке, меньшие квадрата его первого числа, являютсяпростыми.

Решето только по нечётнымчислам


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

Уменьшение объёма потребляемойпамяти


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

Решето Эратосфена с линейным временемработы


 Этот алгоритм обнаруживает для каждого числа в отрезке его минимальныйпростой делитель .
 Также поддерживается список всех простых чисел — массив , поначалупустой. В ходе работы алгоритма этот массив будет постепеннозаполняться.
 Изначально все величины заполним нулями.
 Дальше следует перебрать текущее число от до . Здесь может быть дваслучая:

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

 Следовательно, надо присвоить и добавить в конец списка .

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

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

agraphПсевдокод
 \texttt \textttВход\texttt: натуральное число \textttn\\\\\textttПусть \textttpr\texttt - целочисленный массив, поначалу пустой;\\\texttt      \textttlp\texttt - целочисленный массив, индексируемый от 2 до \textttn\texttt, заполненный нулями\\\\\texttt \textttдля\texttt \texttti\texttt := 2, 3, 4, ..., \textttдо\texttt \textttn\texttt: \\\texttt   \textttесли\texttt \textttlp\texttt[\texttti\texttt] = \texttt0\texttt:\\\texttt       \textttlp\texttt[\texttti\texttt] := \texttti\\\texttt       \textttpr\texttt[] += \{\texttti\texttt\}\\\texttt   \textttдля\texttt \textttp\texttt из \textttpr\texttt пока \textttp\texttt ≤ \textttlp\texttt[\texttti\texttt] и \textttp*i\texttt ≤ \textttn\texttt:\\\texttt       \textttlp\texttt[\textttp*i\texttt] := \textttp\\\\\textttВыход\texttt: все числа в массиве \textttpr\texttt.