Просмотр кода страницы Решето Эратосфена

'''Решето́ Эратосфе́на''' — [[алгоритм]] нахождения всех [[простое число|простых чисел]] до некоторого целого числа {{math|''n''}}, который приписывают древнегреческому математику [[Эратосфен|Эратосфену Киренскому]]<ref name="nicomachus">[[Никомах Герасский]], ''Введение в арифметику'', I, XIII, 2. [https://archive.org/stream/nicomachigerasen00nicouoft#page/29/mode/1up по-гречески], [https://classics.nsu.ru/schole/3/3-1-nicomach-2.pdf по-русски] {{Wayback|url=https://classics.nsu.ru/schole/3/3-1-nicomach-2.pdf |date=20220401141606 }}</ref>. Название алгоритма говорит о принципе его работы: алгоритм осуществляет [[Фильтр (математика)|фильтрацию]] списка чисел от 2 до {{math|''n''}}. По мере прохождения списка [[составное число|составные]] числа исключаются, а простые остаются.

== История ==
[[Файл:Снимок экрана 2024-07-30 в 00.16.23.png|мини|Решето Эратосфена в греческом издании Никомаха ([[Греческие цифры|греческие числа]]: {{nobr|γ - 3,}} {{nobr|ε - 5,}} {{nobr|ζ - 7,}} {{nobr|θ - 9,}} {{nobr|ια - 11, ...)}}<ref>{{Книга|ссылка=https://archive.org/details/nicomachigerasen00nicouoft/page/30/mode/2up?view=theater|автор={{nobr|Hoche R.}}|заглавие=Nicomachi Geraseni Pythagorei Introductionis Arithmeticae libri II (Lipsiae)|ответственный=ed.|год=1866|язык=gr}}</ref>]][[Файл:Снимок экрана 2024-07-30 в 00.09.39.png|мини|Первый, опубликованный в новое время, анализ метода решета Эратосфена и его доказательство {{iw|Хорсли, Сэмюэл|Хорсли|en|Samuel Horsley}}<ref name="horsley" />]]
Этот метод описан во «Введении в арифметику» [[Никомах Герасский|Никомаха Герасского]]. Никомах называет автором метода [[Эратосфен]]а. То же делает и [[Ямвлих]] в своём комментарии к этому сочинению Никомаха.

Название «решето» метод получил потому, что во времена Эратосфена писали числа на дощечке, покрытой воском, и прокалывали дырочки в тех местах, где были написаны [[составное число|составные числа]]. Поэтому дощечка являлась неким подобием решета, через которое «просеивались» все составные числа, а оставались только числа простые<ref>{{книга|автор=[[Депман, Иван Яковлевич|Депман И. Я.]]|заглавие=История арифметики. Пособие для учителей|место=М.|издательство=[[Просвещение (издательство)|Просвещение]]|год=1965|страницы=133|тираж=34000}}</ref>.

Никомах, во II веке н. э., объясняет, что метод решета «высеивает» простые числа из нечётных, отделяя от них составные числа, которые он находит, перечисляя для каждого нечетного числа ''n'' каждое ''n''-ное число в ряду нечётных чисел, начиная с ''n''. Число 2 он здесь не рассматривал, так как в качестве возможно простых чисел он рассматривал только нечётные<ref name="nicomachus" />.

Символически, используя знак " {{math|\}} " как «разность множеств», его весьма многословное словесное описание выражает алгоритм<small>

   '''''Primes'' = {3,5,7,9,...} \ ''Composites'''''
   &nbsp;
   '''''Composites'' = { 3''n'',5''n'',7''n'',9''n'',... for ''n'' in {3,5,7,9,...} }'''</small>

Британец {{iw|Хорсли, Сэмюэл|Хорсли|en|Samuel Horsley}}, 16 веков спустя, горячо критикует это описание, заявляя что «истинный» метод Эратосфена «наверняка» был «гораздо умнее», начиная с ''квадратов'' самих ''простых чисел'' прямо в процессе их распознавания<ref name="horsley" />:<small>

   '''''Primes'' = {3,5,7,9,...} \ ''Composites'''''
   &nbsp;
   '''''Composites'' = { ''n²'',''n²''+2''n'',''n²''+4''n'',... for ''n'' in ''Primes'' }'''</small>

== Алгоритм ==
[[Файл:New Animation Sieve of Eratosthenes.gif|right|400px|Анимация шагов алгоритма Эратосфена для нахождения простых чисел до 120]]
Для нахождения всех простых чисел не больше заданного числа ''n'', следуя методу Эратосфена, нужно выполнить следующие шаги:
# Выписать подряд все целые числа от двух до ''n'' (2, 3, 4, …, ''n'').
# Пусть переменная ''p'' изначально равна двум — первому простому числу.
# Зачеркнуть в списке числа от 2''p'' до ''n,'' считая шагами по ''p'' (это будут числа, кратные ''p'': 2''p'', 3''p'', 4''p'', …).
# Найти первое незачёркнутое число в списке, большее чем ''p'', и присвоить значению переменной ''p'' это число.
# Повторять шаги 3 и 4, пока возможно.

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

На практике, алгоритм можно улучшить следующим образом. На шаге № 3 числа можно зачеркивать, начиная сразу с числа ''p''<sup>2</sup>, потому что все меньшие числа, кратные p, обязательно имеют простой делитель меньше p, и они уже будут зачеркнуты к этому времени. И, соответственно, останавливать алгоритм можно, когда ''p''<sup>2</sup> станет больше, чем ''n''.<ref name="horsley" /> Кроме того, все простые числа, кроме 2, — нечётные числа, и поэтому для них можно считать шагами по 2''p'', начиная с ''p''<sup>2</sup>.

== Пример для n = 30 ==
Запишем натуральные числа, начиная от {{math|2}}, до {{math|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

Первое число в списке, {{math|2}} — простое. Пройдём по ряду чисел, зачёркивая все числа, кратные {{math|2}} (то есть, каждое второе, начиная с {{math|2<sup>2</sup> {{=}} 4}}):

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

Следующее незачеркнутое число, {{math|3}} — простое. Пройдём по ряду чисел, зачёркивая все числа, кратные {{math|3}} (то есть, каждое третье, начиная с {{math|3<sup>2</sup> {{=}} 9}}):

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

Следующее незачеркнутое число, {{math|5}} — простое. Пройдём по ряду чисел, зачёркивая все числа, кратные 5 (то есть, каждое пятое, начиная с {{math|5<sup>2</sup> {{=}} 25}}):

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

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

 2  3     5     7           11    13          17    19          23                29

== Псевдокод ==
Оптимизированная реализация (начинающаяся с квадратов) на [[Псевдокод (язык описания алгоритмов)|псевдокоде]]<ref name="sedgewick">{{книга
|заглавие=Algorithms in C++
|ссылка=https://archive.org/details/algorithmsinc0000sedg
|издательство=[[Addison-Wesley]]
|год=1992
|isbn=0-201-51059-6
|язык=und
|автор=Sedgewick, Robert
}}, p. 16.</ref><ref name="intro">[ftp://ftp.cs.wisc.edu/pub/techreports/1990/TR909.pdf 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).</ref>:

 '''Вход''': натуральное число ''n''
 '''Выход''': все простые числа от 2 до ''n''.
 
 '''Пусть''' ''A'' — [[Логический тип|булевый]] массив, индексируемый числами от 2 до ''n'', 
 изначально заполненный значениями '''true'''.
 
  '''для''' ''i'' = 2, 3, 4, ..., '''пока''' ''i''<sup>2</sup> &le; ''n'':
   '''если''' ''A''[''i''] = '''true''':
     '''для''' ''j'' = ''i''<sup>2</sup>, ''i''<sup>2</sup> + ''i'', ''i''<sup>2</sup> + 2''i'', ..., '''пока''' ''j'' &le; ''n'':
       '''назначить''' ''A''[''j''] := '''false'''
 
  '''возвращаем''': все числа ''i'', для которых ''A''[''i''] = '''true'''.

== Сложность алгоритма ==
[[Временная сложность алгоритма|Сложность алгоритма]] составляет <math>O(n \log (\log n))</math> операций при составлении таблицы простых чисел до <math>n</math><ref>Pritchard, Paul, "Linear prime-number sieves: a family tree, " ''Sci. Comput. Programming'' '''9''':1 (1987), pp. 17-35.</ref>.

=== Доказательство сложности ===
При выбранном <math>n \in \mathbb{N}</math> для каждого простого <math>p \in \mathbb{P}\colon p \le n</math> будет выполняться внутренний цикл<ref>Строго говоря, внутренний цикл выполняется для каждого простого <math>p \in \mathbb{P}\colon p \le (\sqrt n)</math>, но <math>O(\log (\log n))</math> = <math>O(\log (\log (\sqrt n)))</math>, поэтому, традиционно, для краткости, квадратный корень опускают.</ref>, который совершит <math>\frac{n}{p}</math> действий. Сложность алгоритма можно получить из оценки следующей величины:

<math> \sum\limits_{p\in \mathbb{P}\colon p \le n} {\frac{n}{p}} = n\cdot\sum\limits_{p\in \mathbb{P}\colon p \le n} {\frac{1}{p}} </math>

Так как количество [[простое число|простых чисел]], меньших либо равных <math>n</math>, [[Теорема о распределении простых чисел|оценивается]] как <math>\frac{n}{\ln n}</math>, и, как следствие, <math>k</math>-е простое число примерно равно <math>k\ln k</math>, то сумму можно преобразовать:

<math> \sum\limits_{p \in \mathbb{P}\colon p \le n}\frac{1}{p}\approx \frac{1}{2} + \sum\limits_{k=2}^{\frac{n}{\ln n}}\frac{1}{k\ln k}</math>

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

<math> \frac{1}{2} + \sum^{\frac{n}{\ln n}}_{k=2}{\frac{1}{k\ln k}} \approx \int\limits_2^{\frac{n}{\ln n}} {\frac{1}{k\ln k}}\,dk   =  \ln \ln k \Bigr|_2^{\frac{n}{\ln n}} = \ln \ln {\frac{n}{\ln n}} - \ln \ln 2 = \ln (\ln n - \ln \ln n) - \ln \ln 2 \approx \ln \ln n </math>

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

<math> \sum\limits_{p\in \mathbb{P}\colon p \le n} {\frac{n}{p}}  \approx n \ln \ln n + o(n)</math>

Более строгое доказательство (и дающее более точную оценку с точностью до константных множителей) можно найти в книге Hardy и Wright «An Introduction to the Theory of Numbers»<ref name="автоссылка2">[https://archive.org/stream/AnIntroductionToTheTheoryOfNumbers-4thEd-G.h.HardyE.m.Wright#page/n363/mode/2up Hardy and Wright "An Introduction to the Theory of Numbers, p. 349]</ref>.

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

=== Неограниченный, постепенный вариант ===
В этом варианте простые числа вычисляются последовательно, без ограничения сверху,<ref name="ONeill">O’Neill, Melissa E., [http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf «The Genuine Sieve of Eratosthenes»] {{Wayback|url=http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf |date=20171109043858 }}, Journal of Functional Programming, Published online by Cambridge University Press 9 October 2008 {{doi|10.1017/S0956796808007004}}.</ref> как числа, находящиеся в промежутках между составными числами, которые вычисляются для каждого простого числа {{math|''p''}}, начиная с его квадрата, с шагом в {{math|''p''}} (или для нечетных простых чисел {{math|''2p''}})<ref name="horsley">Horsley, Rev. Samuel, F. R. S., "''{{lang|el|Κόσκινον Ερατοσθένους}}'' or, The Sieve of Eratosthenes. Being an Account of His Method of Finding All the Prime Numbers, " [https://www.jstor.org/stable/106053 ''Philosophical Transactions'' (1683—1775), Vol. 62. (1772), pp. 327—347] {{Wayback|url=https://www.jstor.org/stable/106053 |date=20181002215249 }}.</ref>. Может быть представлен абстрактно в парадигме [[Программирование потоков данных|потоков данных]] как<small>

  '''''primes'' = {''2'',''3'',...} \ { ''p²'', ''p²''+''p'', ... for ''p'' in ''primes'' }'''</small>

используя нотацию [[Списковое включение|абстракции списков]], где <code>\</code> обозначает [[разность множеств|разницу]] между [[Арифметическая прогрессия|арифметическими прогрессиями]].

Первое простое число {{math|''2''}} (среди [[Монотонная последовательность|возрастающих]] положительных [[Натуральное число|целых чисел]]) заранее известно, поэтому в этом [[Самореференция|самореферентном]] определении нет [[Порочный круг|порочного круга]].

Более конкретный псевдокод с поэтапным отсеиванием, в неэффективной реализации, для простоты сравнения с нижеследующими вариантами: <small>
  '''''primes'' = sieve [''2..''] where'''
     '''sieve [''p'', ...''xs''] = [''p'', ...sieve (''xs'' \ [''p²'', ''p²''+''p''..])]'''</small>
<!--
     '''sieve [''p'', ...''xs''] = [''p'', ...sieve (''xs'' \ [''p''*''n'' for ''n'' in [''p''..]])]'''
-->

Более эффективный вариант отделяет на каждом шагу из начала списка не одно лишь первое число, а сразу все числа не превосходящие квадрата очередного простого числа. Это реализуется посредством откладывания отсеивания каждым простым числом, до его квадрата:<small>
  '''''primes'' = [''2'', ...sieve ''primes'' [''3..'']] where'''
     '''sieve [''p'', ...''ps''] [...''h'', ''p²'', ...''xs'']'''
          '''= [...''h'', ...sieve ''ps'' (''xs'' \ [''p²'', ''p²''+''p''..])]'''</small>

=== Перебор делителей ===
Решето Эратосфена часто путают с алгоритмами, которые поэтапно {{iw|Фильтр (программирование)|отфильтровывают|en|Filter (higher-order function)}} [[Составное число|составные числа]], ''тестируя'' каждое из чисел-кандидатов на делимость по одному простому числу на каждом этапе.<ref name="Runciman">Colin Runciman, [http://portal.acm.org/citation.cfm?id=969898 «FUNCTIONAL PEARL: Lazy wheel sieves and spirals of primes»], Journal of Functional Programming, Volume 7 Issue 2, March 1997; также [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.55.7096&rank=3 здесь] {{Wayback|url=http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.55.7096&rank=3 |date=20121019203557 }}.</ref>

Широко известный [[Функциональное программирование|функциональный]] код [[Тёрнер, Дэвид|Дэвида Тёрнера]] 1975 г.<ref>Turner, David A. SASL language manual. Tech. rept. CS/75/1. Department of Computational Science, University of St. Andrews 1975. (<code>primes = sieve [2..]; sieve (p:nos) = p:sieve (remove (multsof p) nos); remove m = filter (not . m); multsof p n = rem n p==0</code>)</ref> часто принимают за решето Эратосфена,<ref name="Runciman"/> но на самом деле<ref name="ONeill" /> это неоптимальный вариант с [[Перебор делителей|перебором делителей]]: <small>
  '''''primes'' = sieve [''2..''] where'''
     '''sieve [''p'', ...''xs''] = [''p'', ...sieve [''x'' in ''xs'' if ''x%p'' > ''0'']]'''</small>
В оптимальном варианте не используются делители, большие квадратного корня тестируемого числа.
<!-- Этого можно достичь отложенным отсеиванием, <small>
  '''''primes'' = [''2'', ...sieve( ''primes'', [''3..''])]  where'''
    '''sieve( [''p'', ...''ps''], [...''h'', ''p²'', ...''xs'']) =''' 
         =  '''[''...h'', ...sieve( ''ps'', ''xs'' \ [''p²'', ''p²''+''p''..])]'''
         =  '''[''...h'', ...sieve( ''ps'', [''x'' in ''xs'' if ''x%p'' > ''0''])]'''</small>
-->

=== Сегментированное решето ===
Как замечает Соренсон, главной проблемой реализации решета Эратосфена на вычислительных машинах является не количество выполняемых операций, а требования по объёму занимаемой памяти (впрочем, его замечание относится к неактуальному сейчас компьютеру DEC VAXstation 3200, выпущенному в 1989 году).{{r|intro}} При больших значениях {{mvar|n}}, диапазон простых чисел может превысить доступную память; хуже того, даже при сравнительно небольших {{mvar|n}} использование [[кэш]]а памяти далеко от оптимального, так как алгоритм, проходя по всему массиву, нарушает принцип {{iw|локализованность ссылок|локализованности ссылок||locality of reference}}.

Для решения представленной проблемы используется сегментированное решето, в котором за итерацию просеивается только часть диапазона простых чисел.<ref>Crandall & Pomerance, ''Prime Numbers: A Computational Perspective'', second edition, Springer: 2005, pp. 121-24.</ref> Данный метод известен с 1970-х годов и работает следующим образом:{{r|intro}}<ref name="автоссылка4">{{статья |заглавие=The segmented sieve of Eratosthenes and primes in arithmetic progressions to 10<sup>12</sup> |издание=BIT |том=17 |номер=2 |страницы=121—127 |doi=10.1007/BF01932283 |язык=en |тип=journal |автор=Bays, Carter; Hudson, Richard H. |год=1977}}</ref>

# Разделяем диапазон от 2 до {{mvar|n}} на отрезки (сегменты) некоторой длины {{math|Δ ≤ {{sqrt|''n''}}}}.
# Находим все простые числа в первом отрезке, используя обычное решето.
# Каждый из последующих отрезков оканчивается на некотором числе {{mvar|m}}. Находим все простые числа в отрезке следующим образом:
## Создаем булевый массив размера {{math|Δ}}
## Для каждого простого числа {{math|''p'' ≤ {{sqrt|''m''}}}} из уже найденных, отмечаем в массиве как «непростые» все числа кратные {{math|''p''}}, перебирая числа с шагом в {{math|''p''}}, начиная с наименьшего кратного {{math|''p''}} числа в данном отрезке.

Если число {{math|Δ}} выбрано равным {{math|{{sqrt|''n''}}}}, то сложность алгоритма по памяти оценивается как {{math|''O''({{sqrt|''n''}})}}, а операционная сложность остаётся такой же, что и у обычного решета Эратосфена.<ref name="автоссылка4" />

Для случаев, когда {{mvar|n}} настолько велико, что все просеиваемые простые числа меньшие {{math|{{sqrt|''n''}}}} не могут уместиться в памяти, как того требует алгоритм сегментированного сита, используют более медленные, но с гораздо меньшими требованиями по памяти алгоритмы, например [[решето Соренсона]].<ref>J. Sorenson, [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.94.1737 The pseudosquares prime sieve] {{Wayback|url=http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.94.1737 |date=20121017014228 }}, Proceedings of the 7th International Symposium on Algorithmic Number Theory. (ANTS-VII, 2006).</ref>

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

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

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

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

В псевдокоде, <!--
  '''''primes'' = sieve [''2..''] where'''
     '''sieve [''p'', ...''xs''] = [''p'', ...sieve (''xs'' \ [''p²'', ...[''p''*''x'' for ''x'' in ''xs'']])]'''

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

  '''''primes'' = sieve [''2..''] where'''
     '''sieve [''p'', ...''xs''] = [''p'', ...sieve (''xs'' \ ''p''*[''p'', ...''xs''])]'''-->

  <small>'''''primes'' = sieve [''2..''] where'''
     '''sieve [''p'', ...''xs''] = [''p'', ...sieve (''xs'' \ [''p²'', ...''p''*''xs''])]'''</small>

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

В псевдокоде:
<small>
  '''''primes'' = [2, ...sieve [''3,5..'']] where'''
     '''sieve [''p'', ...''xs''] = [''p'', ...sieve (''xs'' \ [''p²'', ''p²''+''2p''..])]'''</small>
<!--
     '''sieve [''p'', ...''xs''] = [''p'', ...sieve (''xs'' \ [''p''*''n'' for ''n'' in [''p''..]])]'''
-->
Это можно обобщить на числа [[Взаимно простые числа|взаимно простые]] не только с 2 (то есть нечетные числа), но также и с [[Кольцевая факторизация|3, 5, и т. д.]].

=== Уменьшение объёма потребляемой памяти ===
Алгоритм Эратосфена фактически оперирует с <math>n</math> [[бит]]ами памяти. Следовательно, можно существенно сэкономить потребление памяти, храня <math>n</math> переменных булевского типа не как <math>n</math> [[байт]], а как <math>n</math> бит, то есть <math>n/8</math> байт памяти.

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

=== Решето Эратосфена с линейным временем работы ===
Этот алгоритм находит составные числа как перечисление формулы<small>

 { (''p<sup>i</sup>q<sup>j</sup>r<sup>k</sup>''...) '''for''' ''p'',''q'',''r'',... '''in''' ''primes'', '''where''' ''i''+''j''+''k''+... > 1 }</small>

Для этого поддерживается список простых чисел {{math|pr[]}}, поначалу пустой. В ходе работы алгоритма этот список будет постепенно дополняться и в конце работы будет содержать все простые числа от {{math|2}} до {{math|n}}.

Также поддерживается массив {{math|lp[]}} ({{math|lp}} от {{lang-en|least prime}}) где для всех {{math|i}} от {{math|2}} до {{math|n}}, {{math|lp[i]}} будет содержать минимальный простой делитель числа {{math|i}}. Изначально все величины {{math|lp[i]}} равны {{math|0}}.

Дальше перебираем числа {{math|i}} от {{math|2}} до {{math|n}} в порядке возрастания. Для каждого {{math|i}}:

: 1. Если {{math|lp[i] &ne; 0}}, это означает, что текущее число {{math|i}} — составное, и его минимальным простым делителем является {{math|lp[i]}}.

: 2. Если {{math|lp[i] {{=}} 0}}, это означает, что текущее число {{math|i}} — простое, так как для него так и не обнаружилось других делителей. Присваиваем {{math|lp[i] {{=}} i}} и добавляем {{math|i}} в конец списка {{math|pr[]}}.

: 3. Итак, {{math|lp[i]}} является минимальным простым делителем числа {{math|i}}. Для всех {{math|p}} последовательно взятых из {{math|pr[]}}, не превосходящих {{math|lp[i]}}, назначаем {{math|lp[p &sdot; i] {{=}} p}}.

Утверждается, что таким образом каждое значение в {{math|lp[]}} назначается только один раз<ref>David Gries, Jayadev Misra. A Linear Sieve Algorithm for Finding Prime Numbers [1978]</ref>.

==== Псевдокод ====
 
  '''Вход''': натуральное число ''n''
 
  Пусть ''pr'' - целочисленный список, поначалу пустой;
        ''lp'' - целочисленный массив, индексируемый от 2 до ''n'', заполненный нулями
 
  '''для''' ''i'' := 2, 3, 4, ..., '''до''' ''n'': 
    '''если''' ''lp''[''i''] = '''0''':
        ''lp''[''i''] := ''i''
        ''pr''[] += {''i''}
    '''для''' ''p'' из ''pr'' пока ''p'' &le; ''lp''[''i''] и ''p*i'' &le; ''n'':
        ''lp''[''p*i''] := ''p''
 
 '''Выход''': все числа в списке ''pr''.

== Сложность алгоритма на практике ==
Решето Эратосфена является популярным способом оценки производительности компьютера.<ref name="peng1985fall">{{cite news | url=https://archive.org/stream/byte-magazine-1985-11/1985_11_BYTE_10-11_Inside_the_IBM_PCs#page/n245/mode/2up | title=One Million Primes Through the Sieve | work=BYTE | date=Fall 1985 | accessdate=2016-03-19 | author=Peng, T. A. | pages=243–244}}</ref> Как видно из вышеизложенного [[Решето Эратосфена#Доказательство сложности|доказательства сложности]] алгоритма, избавившись от константы и слагаемого очень близкого к нулю{{math| (ln (ln ''n'' - ln ln ''n'') - ln ln 2 ''≈'' ln ln ''n'')}}, временная сложность вычисления всех простых чисел меньше {{mvar|n}} аппроксимируется следующим соотношением {{math|''O''(''n'' ln ln ''n'')}}. Однако алгоритм имеет экспоненциальную временную сложность в отношении размера входных данных, что делает его [[Псевдополиномиальный алгоритм|псевдополиномиальным алгоритмом]]. Памяти же для базового алгоритма требуется {{math|''O''(''n'')}}.<ref name="Pritchard1">Paul Pritchard, A sublinear additive sieve for finding prime numbers, Communications of the ACM 24 (1981), 18-23. {{MR|600730}}</ref>

[[Решето Эратосфена#Сегментированное решето|Сегментированная версия]] имеет ту же операционную сложность {{math|''O''(''n''  ln ln ''n'')}},<ref name="автоссылка2" />. что и несегментированная версия, но уменьшает потребность в используемой памяти до размера сегмента (размер сегмента значительно меньше размера всего массива простых чисел), который равен {{math|''O''(√''n''/ln ''n'')}}.<ref name="Pritchard3">Paul Pritchard, Fast compact prime number sieves (among others), Journal of Algorithms 4
(1983), 332—344. {{MR|729229}}</ref>
Также существует очень редко встречающееся на практике оптимизированное сегментированное решето Эратосфена. Оно строится за {{math|''O''(''n'')}} операций и занимает {{math|''O''(''√n'' ln ln ''n''/ln ''n'')}} бит в памяти.<ref name="Pritchard1" /><ref name="Pritchard3" /><ref name="Pritchard2">Paul Pritchard, Explaining the wheel sieve, Acta Informatica 17 (1982), 477—485. {{MR|685983}}</ref>

На практике оказывается, что оценка {{math|ln ln ''n''}} не очень точна даже для максимальных практических диапазонов таких как 10<sup>16</sup>.<ref name="Pritchard2" /> Ознакомившись с вышеописанным [[Решето Эратосфена#Доказательство сложности|доказательством сложности]], нетрудно понять откуда взялась неточность оценки. Расхождение с оценкой можно объяснить следующим образом: в пределах данного практического диапазона просеивания существенное влияние оказывают постоянные смещения.<ref name="автоссылка2" /> Таким образом очень медленно растущий член {{math|ln ln ''n''}} не становится достаточно большим, чтобы константами можно было справедливо пренебречь, до тех пор пока {{mvar|n}} не приблизится к бесконечности, что естественно выходит за границы любого прикладного диапазона просеивания.<ref name="автоссылка2" /> Данный факт показывает, что для актуальных на сегодняшний день входных данных производительность решета Эратосфена намного лучше, чем следовало ожидать, используя только асимптотические оценки временной сложности.<ref name="Pritchard2" />

Решето Эратосфена работает быстрее, чем часто сравниваемое с ним [[решето Аткина]] только для значений {{mvar|n}} меньших 10 <sup> 10 </sup>.<ref name="автоссылка5">{{Статья|автор=A. O. L. ATKIN AND D. J. BERNSTEIN|заглавие=PRIME SIEVES USING BINARY QUADRATIC FORMS|ссылка=http://www.ams.org/journals/mcom/2004-73-246/S0025-5718-03-01501-1/S0025-5718-03-01501-1.pdf|язык=|издание=MATHEMATICS OF COMPUTATION|тип=|год=|месяц=|число=|том=|номер=|страницы=|issn=|archivedate=2017-12-24|archiveurl=https://web.archive.org/web/20171224143024/http://www.ams.org/journals/mcom/2004-73-246/S0025-5718-03-01501-1/S0025-5718-03-01501-1.pdf}}</ref> Сказанное справедливо при условии, что операции занимают примерно одно и то же время в циклах [[Центральный процессор|центрального процессора]], а это является разумным предположением для одного алгоритма, работающего с огромным битовым массивом.<ref name="автоссылка6">{{Статья|автор=Meertens, Lambert|заглавие=Calculating the Sieve of Eratosthenes|ссылка=|язык=|издание=Journal of
functional programming|тип=|год=|месяц=|число=|том=|номер=|страницы=|issn=}}</ref> С учётом этого предположения получается, что сито Аткина быстрее чем максимально факторизованное решето Эратосфена для {{mvar|n}} свыше 10 <sup> 13 </sup>, но при таких диапазонах просеивания потребуется занять огромное пространство в оперативной памяти, даже если была использована «битовая упаковка».<ref name="автоссылка6" /> Однако раздел о [[Решето Эратосфена#Сегментированное решето|сегментированной версии решета Эратосфена]] показывает, что предположение о сохранении равенства во времени, затрачиваемом на одну операцию, между двумя алгоритмами не выполняется при сегментации.<ref name="автоссылка4" /><ref name="автоссылка5" /> В свою очередь это приводит к тому, что решето Аткина (несегментированное) работает медленнее, чем сегментированное решето Эратосфена с увеличением диапазона просеивания, за счёт уменьшения времени на операцию для второго.

Использование нотации {{math|''O''}} большого также не является правильным способом сравнения практических характеристик даже для вариаций решета Эратосфена, поскольку данная нотация игнорирует константы и смещения, которые могут быть очень значительными для прикладных диапазонов.<ref name="автоссылка2" /> Например, одна из вариаций решета Эратосфена известная как решето Притчарда<ref name="Pritchard1" /> имеет производительность {{math|''O''(''n'')}},<ref name="Pritchard2" /> но её базовая реализация требует либо алгоритма «одного большого массива»<ref name="Pritchard3" /> (то есть использования обычного массива, в котором хранятся все числа до {{math| ''n''}}), который ограничивает его диапазон использования до объёма доступной памяти, либо он должен быть сегментирован для уменьшения использования памяти. Работа Притчарда уменьшила требования к памяти до предела, но платой за данное улучшение по памяти является усложнение вычислений, что приводит увеличению операционной сложности алгоритмов.<ref name="Pritchard2" />

Популярным способом ускорения алгоритмов, работающих с большими массивами чисел, является разного рода [[факторизация]].<ref name="автоссылка7">{{Статья|автор=В.А. Минаев, Н.П. Васильев, В.В. Лукьянов, С.А. Никонов, Д.В. Никеров|заглавие=ИНДЕКСНЫЕ АЛГОРИТМЫ
ВЫЧИСЛЕНИЯ ПРОСТЫХ ЧИСЕЛ
С ИСПОЛЬЗОВАНИЕМ МЕТОДА
КОЛЬЦЕВОЙ ФАКТОРИЗАЦИИ|ссылка=http://vestnik-rosnou.ru/pdf/n4y2013/p29.pdf|язык=|издание=ВЕСТНИК|тип=|год=2013|месяц=|число=|том=|номер=4|страницы=29|issn=|archivedate=2017-12-22|archiveurl=https://web.archive.org/web/20171222105242/http://vestnik-rosnou.ru/pdf/n4y2013/p29.pdf}}</ref> Применение методов факторизации даёт значительное уменьшение операционной сложности за счёт оптимизации входного массива данных.<ref name="автоссылка7" /><ref name="автоссылка1">{{Статья|автор=Jonathan Sorenson|заглавие=An Analysis of Two Prime Number Sieves|ссылка=ftp://ftp.cs.wisc.edu/pub/techreports/1991/TR1028.pdf|язык=|издание=Computer Sciences Department University of Wisconsin-Madison|тип=|год=|месяц=|число=|том=|номер=|страницы=8—10|issn=}}</ref> Для индексных алгоритмов часто используют кольцевую факторизацию.<ref name="автоссылка1" /><ref>{{Статья|автор=В.А. Минаев, Н.П. Васильев, В.В. Лукьянов, С.А. Никонов, Д.В. Никеров|заглавие=ИНДЕКСНЫЕ АЛГОРИТМЫ
ВЫЧИСЛЕНИЯ ПРОСТЫХ ЧИСЕЛ
С ИСПОЛЬЗОВАНИЕМ МЕТОДА
КОЛЬЦЕВОЙ ФАКТОРИЗАЦИИ|ссылка=http://vestnik-rosnou.ru/pdf/n4y2013/p29.pdf|язык=|издание=ВЕСТНИК|тип=|год=2013|месяц=|число=|том=|номер=4|страницы=30—31|issn=|archivedate=2017-12-22|archiveurl=https://web.archive.org/web/20171222105242/http://vestnik-rosnou.ru/pdf/n4y2013/p29.pdf}}</ref> Рассматриваемые в данной статье алгоритмы нахождения всех простых чисел до заданного {{math|n}} подобные решету Эратосфена относятся к индексным, что позволяет применять к ним метод кольцевой факторизации.<ref>{{Статья|автор=В.А. Минаев, Н.П. Васильев, В.В. Лукьянов, С.А. Никонов, Д.В. Никеров|заглавие=ИНДЕКСНЫЕ АЛГОРИТМЫ
ВЫЧИСЛЕНИЯ ПРОСТЫХ ЧИСЕЛ
С ИСПОЛЬЗОВАНИЕМ МЕТОДА
КОЛЬЦЕВОЙ ФАКТОРИЗАЦИИ|ссылка=http://vestnik-rosnou.ru/pdf/n4y2013/p29.pdf|язык=|издание=ВЕСТНИК|тип=|год=2013|месяц=|число=|том=|номер=4|страницы=30—33|issn=|archivedate=2017-12-22|archiveurl=https://web.archive.org/web/20171222105242/http://vestnik-rosnou.ru/pdf/n4y2013/p29.pdf}}</ref>

Несмотря на теоретическое ускорение, получаемое с помощью [[Кольцевая факторизация|кольцевой факторизации]], на практике существуют факторы, которые не учитываются при расчётах, но способны оказать существенное влияние на поведение алгоритма, что в результате может не дать ожидаемого прироста в быстродействии.<ref>{{Статья|автор=Jonathan Sorenson|заглавие=An Analysis of Two Prime Number Sieves|ссылка=ftp://ftp.cs.wisc.edu/pub/techreports/1991/TR1028.pdf|язык=|издание=Computer Sciences Department University of Wisconsin-Madison|тип=|год=|месяц=|число=|том=|номер=|страницы=16—18|issn=}}</ref> Рассмотрим наиболее существенные из них:

* {{math|Умножение и деление.}} При аналитических расчётах предполагается, что скорость выполнения арифметических операций равноценна. Но на самом деле это не так, и умножение, и деление выполняются гораздо медленнее, чем сложение и вычитание. Таким образом данный фактор никак не влияет на решето Эратосфена, поскольку оно использует только сложение и вычитание, но является весьма существенным для решета Питчарда (один из результатов усложнения вычислений упомянутого выше).<ref>{{Статья|автор=Jonathan Sorenson|заглавие=An Analysis of Two Prime Number Sieves|ссылка=ftp://ftp.cs.wisc.edu/pub/techreports/1991/TR1028.pdf|язык=|издание=Computer Sciences Department University of Wisconsin-Madison|тип=|год=|месяц=|число=|том=|номер=|страницы=16|issn=}}</ref>
* {{math|Оптимизация компилятора.}} Компилятор оптимизирует на стадии компиляции все программы для более корректного исполнения машиной. Но часто бывает очень сложно сказать, какой вклад даёт данная оптимизация, и будет ли этот вклад одинаковым для двух различных алгоритмов.<ref name="автоссылка3">{{Статья|автор=Jonathan Sorenson|заглавие=An Analysis of Two Prime Number Sieves|ссылка=ftp://ftp.cs.wisc.edu/pub/techreports/1991/TR1028.pdf|язык=|издание=Computer Sciences Department University of Wisconsin-Madison|тип=|год=|месяц=|число=|том=|номер=|страницы=17|issn=}}</ref>
* {{math|[[Кэш|Кэш]].}} [[Центральный процессор|Процессор]] использует кэш, чтобы ускорить извлечение инструкций и данных из памяти. Наличие кэша приводит к тому, что программы, использующие локализованные ссылки, будут работать быстрее. Но алгоритмы просеивания простых чисел, которые используют факторизацию высокой степени, часто генерируют случайные ссылки в память, что снижает их производительность.<ref name="автоссылка3" />

Для наглядности представления вклада факторизации в производительность алгоритмов просеивания ниже приведены две таблицы. В таблицах приведены результаты измерения реального времени исполнения решета Эратосфена и решета Питчарда в секундах для разных диапазонов {{math|n}} и разных степеней кольцевой факторизации. {{math|E<sub>i</sub>}} и {{math|P<sub>i</sub>}} обозначения для решета Эратосфена и Питчарда соответственно, где индекс {{math|i}} означает степень кольцевой факторизации. {{math|E<sub>0</sub>}} и {{math|P<sub>0</sub>}} означают отсутствие факторизации.<ref name="автоссылка3" />

: {| class="wikitable"
! {{mvar|n}}
! colspan=1 | {{math|E<sub>0</sub>}}
! colspan=1 | {{math|E<sub>1</sub>}}
! colspan=1 | {{math|E<sub>2</sub>}}
! colspan=1 | {{math|E<sub>3</sub>}}
! colspan=1 | {{math|E<sub>4</sub>}}
! colspan=1 | {{math|E<sub>5</sub>}}
|-
! 500
| 0.00043
| 0.00029
| 0.00027
| 0.00048
| 0.00140
| 0.01035
|-
! 5000
| 0.00473
| 0.00305
| 0.00254
| 0.00293
| 0.00551
| 0.03207
|-
! 50000
| 0.05156
| 0.03281
| 0.02617
| 0.02578
| 0.03164
| 0.10663
|-
! 500000
| 0.55817
| 0.35037
| 0.28240
| 0.28358
| 0.28397
| 0.47028
|-
! 5000000
| 6.06719
| 3.82905
| 3.20722
| 3.25214
| 3.28104
| 3.38455
|}

Из таблицы видно, что лучшую производительность имеет решето Эратосфена со средней степенью факторизации {{math|E<sub>2</sub>}}. Данный факт можно объяснить влиянием кэш-фактора, рассмотренного выше, на алгоритмы с высокой степенью факторизации.

: {| class="wikitable"
! {{mvar|n}}
! colspan=1 | {{math|P<sub>0</sub>}}
! colspan=1 | {{math|P<sub>1</sub>}}
! colspan=1 | {{math|P<sub>2</sub>}}
! colspan=1 | {{math|P<sub>3</sub>}}
! colspan=1 | {{math|P<sub>4</sub>}}
! colspan=1 | {{math|P<sub>5</sub>}}
|-
! 500
| 0.00147
| 0.00074
| 0.00050
| 0.00051
| 0.00095
| 0.00649
|-
! 5000
| 0.01519
| 0.00777
| 0.00527
| 0.00453
| 0.00430
| 0.00973
|-
! 50000
| 0.15507
| 0.08203
| 0.05664
| 0.04843
| 0.04180
| 0.04413
|-
! 500000
| 1.60732
| 0.86254
| 0.61597
| 0.53825
| 0.47146
| 0.43787
|-
! 5000000
| 16.47706
| 9.00177
| 6.57146
| 5.83518
| 5.27427
| 4.88251
|}

С увеличением {{math|n}} соотношение времен становится всё больше в пользу решета Эратосфена, а на диапазоне {{math|n}} = 5000000 оно стабильно быстрее при любых факторизациях. Данный факт ещё раз подтверждает проигрыш в быстродействии решета Питчарда из-за сложных вычислений.<ref name="Pritchard2" />

== См. также ==
* [[Решето Сундарама]]
* [[Решето Аткина]]
* {{iw|Решето Притчарда|Решето Притчарда|en|Sieve of Pritchard}}
* [[Корекурсия]]

== Примечания ==
{{примечания}}

== Литература ==
* {{БСЭ2|Эратосфеново решето|том=49|страницы=141}}
* {{статья |автор=Гальперин Г. |заглавие=«Просто о простых числах» |издание=[[Квант (журнал)|Квант]] |номер=4 |год=1987 |ссылка=http://kvant.mccme.ru/1987/04/prosto_o_prostyh_chislah.htm|страницы=10—14,38}}
* {{книга |ответственный=[[РАН]], [[Институт истории естествознания и техники]], С.-Петерб. фил.; Сост. Матвиевская Г.П. [и др.]; Отв. ред. Невская Н.И |заглавие=Неопубликованные материалы Л.Эйлера по теории чисел |год=1997 |издательство=[[Наука (издательство)|Наука]] |место=СПб.|isbn=5-02-024847-9}}
* {{книга |автор=Проф. Д.Ф.Егоров |заглавие=Элементы теории чисел |год=1923 |издательство=Государственное издательство Москва |ссылка=http://lib.mipt.ru/book/59898 }}{{Недоступная ссылка|date=Ноябрь 2018 |bot=InternetArchiveBot }}
* {{книга |автор=[[Кордемский, Борис Анастасьевич|Кордемский Б. А.]] |заглавие=Математическая смекалка |место=М. |издательство=ГИФМЛ |год=1958 |страниц=576 |ссылка=http://ilib.mccme.ru/djvu/klassik/smekalka.htm}}

== Ссылки ==
{{wikibooks|Реализации алгоритмов/Решето Эратосфена|Решето Эратосфена}}
* [http://kvant.mccme.ru/1974/01/p77.htm Решето Эратосфена от М. Гарднера]
* [http://habrahabr.ru/post/91112/ Алгоритм составления таблицы простых чисел от заданного до другого числа]
* [http://www.mkyong.com/java/how-to-determine-a-prime-number-in-java/ Реализация алгоритма поиска простых чисел на Java]
* [http://e-maxx.ru/algo/eratosthenes_sieve Доказательство сложности алгоритма]
* [http://habrahabr.ru/post/133037/ Еще раз о поиске простых чисел]
{{ВС}}

[[Категория:Теоретико-числовые алгоритмы]]
[[Категория:Алгоритмы]]