Сито Эратосфена

Сито Эратосфена: шаги алгоритма для простых чисел меньше 121 (включая оптимизацию, начиная с квадрата простого числа).

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

Он делает это путем итеративной маркировки как составных (т. Е. Не простых) кратных каждого простого числа, начиная с первого простого числа, 2. Кратные данного простого числа генерируются как последовательность чисел, начиная с этого простого числа, с постоянной разницей. между ними то же самое, что и простое число. ^[1] Это ключевое отличие решета от использования пробного деления для последовательной проверки каждого числа кандидатов на делимость на каждое простое число. ^[2] После того, как все кратные каждого обнаруженного простого числа были отмечены как составные, оставшиеся неотмеченные числа станут простыми числами.

Самая ранняя известная ссылка на сито ( древнегреческая : κόσκινον Ἐρατοσθένους , kóskinon Eratosthénous ) находится в Никомаха Герасского «ы Введения в арифметику , ^[3] ранний второй цент. Книга н.э., которая описывает его и приписывает Эратосфену Киренскому , III в. До н.э. Греческий математик .

Одно из множества сит простых чисел , это один из наиболее эффективных способов найти все меньшие простые числа. Его можно использовать для поиска простых чисел в арифметических прогрессиях . ^[4]

Обзор [ править ]

Просейте двойку и просейте тройку,
Сито Эратосфена.
Когда кратные возвышаются,
числа, которые остаются, являются простыми.

Анонимный ^[5]

Простое число является натуральное число , которое имеет ровно два различных натуральное число делителей : число 1 и само по себе.

Чтобы найти все простые числа, меньшие или равные заданному целому числу $n$ методом Эратосфена:

Создайте список последовательных целых чисел от 2 до $n$ : $(2, 3, 4, ..., n)$ .
Сначала пусть $p$ равно 2, наименьшему простому числу.
Перечислите числа, кратные $p$ , отсчитывая с шагом $p$ от $2 p$ до $n$ , и отметьте их в списке (это будут $2 p, 3 p, 4 p, ...$ ; сам $p$ не должен быть отмечен).
Найдите наименьшее число в списке больше $p$ , которое не отмечено. Если такого числа не было, остановись. В противном случае пусть $p$ теперь равно этому новому числу (которое является следующим простым числом), и повторите с шага 3.
Когда алгоритм завершается, все числа, не отмеченные в списке, являются простыми числами ниже $n$ .

Основная идея здесь заключается в том, что каждое значение, присвоенное $p,$ будет простым, потому что, если бы оно было составным, оно было бы помечено как кратное некоторому другому, меньшему простому числу. Обратите внимание, что некоторые числа могут быть отмечены более одного раза (например, 15 будет помечено как для 3, так и для 5).

В качестве уточнения достаточно отметить числа на шаге 3, начиная с $p 2$ , так как все меньшие числа, кратные $p$ , уже будут отмечены в этой точке. Это означает, что алгоритму разрешено завершиться на шаге 4, когда $p 2$ больше $n$ . ^[1]

Еще одно усовершенствование состоит в том, чтобы вначале перечислить только нечетные числа $(3, 5, ..., n)$ и считать с шагом $2 p$ от $p 2$ на шаге 3, таким образом отмечая только нечетные числа, кратные $p$ . Это действительно присутствует в исходном алгоритме. ^[1] Это можно обобщить с помощью факторизации колеса , формируя начальный список только из чисел, взаимно простых с первыми несколькими простыми числами, а не только из шансов (т. Е. Чисел, взаимно простых с 2), и подсчитывая соответственно скорректированные приращения, так что только такие кратные числа $p,$ которые в первую очередь взаимно просты с этими маленькими простыми числами. ^[6]

Пример [ править ]

Чтобы найти все простые числа, меньшие или равные 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, считая от 2 с шагом 2 (это будут все числа, кратные 2 в списке):

 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 - 3; вычеркните каждое третье число в списке после 3, считая от 3 с шагом 3 (это будут все числа, кратные 3 в списке):

 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, равно 5; вычеркните каждое 5-е число в списке после 5, считая от 5 с шагом 5 (т.е. все числа, кратные 5):

 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, - 7; следующим шагом будет вычеркнуть каждое седьмое число в списке после 7, но все они уже вычеркнуты на этом этапе, поскольку эти числа (14, 21, 28) также кратны меньшим простым числам, потому что 7 × 7 больше чем 30. Числа, не зачеркнутые в этом месте в списке, - это все простые числа меньше 30:

 2 3 5 7 11 13 17 19 23 29

Алгоритм и варианты [ править ]

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

Сито Эратосфена можно выразить псевдокодом следующим образом: ^[7]^[8]

Алгоритм решето Эратосфена является  вход : целое число п > 1. Выход : все простые числа от 2 -го по п . пусть  A будет массивом логических значений, индексированных целым числом от s 2 до n , изначально все установлено на true .  для  я = 2, 3, 4, ..., не превышающей  $\sqrt п$   делать ,  если [ я ] это верно для J = я ² , я ² + я , я ² +2 я , я ² +3 , я , .. ., не более n do A [ j ]: = false      вернуть все я так , что [ я ] это правда .

Этот алгоритм производит все простые числа не больше $n$ . Он включает в себя общую оптимизацию, которая должна начать перечисление кратных каждого простого числа $i$ от $i 2$ . Временная сложность этого алгоритма $O (п войти журнала п)$ , ^[8] при условии , что обновление массива является $O (1)$ операции, как это обычно имеет место.

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

Как отмечает Соренсон, проблема с ситом Эратосфена не в количестве выполняемых им операций, а скорее в его потребностях в памяти. ^[8] При большом $n$ диапазон простых чисел может не умещаться в памяти; хуже того, даже для умеренного $n$ , его использование кеша крайне неоптимально. Алгоритм проходит по всему массиву $A$ , почти не показывая местоположения ссылки .

Решение этих проблем предлагают сегментированные сита, в которых за раз просеиваются только части диапазона. ^[9] Они известны с 1970-х годов и работают следующим образом: ^[8]^[10]

Разделите диапазон от 2 до $n$ на сегменты некоторого размера $Δ \leq \sqrt n$ .
Найдите простые числа в первом (то есть самом нижнем) сегменте, используя обычное сито.
Для каждого из следующих сегментов в порядке возрастания, где m является самым верхним значением сегмента, найдите в нем простые числа следующим образом:
1. Настройте логический массив размера $Δ$ и
2. Отметьте как непростые позиции в массиве, соответствующие кратным числам каждого простого числа $p \leq \sqrt m,$ найденного на данный момент, путем вычисления наименьшего кратного числа $p$ между $m - Δ$ и $m$ и перечисления его кратных чисел $с$ шагом $p,$ как обычно. Остальные позиции соответствуют простым числам в сегменте, поскольку квадрат простого числа в сегменте не находится в сегменте (при $k \geq 1$ он имеет ). ${\ Displaystyle (к \ Дельта +1) ^ {2}> (к + 1) \ Дельта}$

Если $Δ$ выбрано равным $\sqrt n$ , пространственная сложность алгоритма будет $O (\sqrt n)$ , а временная сложность такая же, как у обычного решета. ^[8]

Для диапазонов с таким большим верхним пределом $n,$ что простые числа просеивания ниже $\sqrt n,$ как того требует сегментированное по страницам сито Эратосфена, не может поместиться в памяти, вместо этого можно использовать более медленное, но гораздо более компактное сито, такое как сито Соренсона . ^[11]

Инкрементальное сито [ править ]

Инкрементальная формулировка решета ^[2] генерирует простые числа на неопределенный срок (т. Е. Без верхней границы) путем чередования генерации простых чисел с генерацией их кратных (так что простые числа могут быть найдены в промежутках между кратными числами), где кратные числа каждое простое число $p$ генерируется прямым отсчетом от квадрата простого числа с приращениями $p$ (или $2 p$ для нечетных простых чисел). Генерация должна быть инициирована только при достижении основного квадрата, чтобы избежать отрицательного воздействия на эффективность. Это может быть выражено символически в парадигме потока данных как

простые числа = [ 2 , 3 , ...] \ [[ p ², p ² + p , ...] для p в простых числах ],

использование нотации понимания списка с \обозначением вычитания множества арифметических прогрессий чисел.

Простые числа также могут быть получены путем итеративного просеивания композитов посредством проверки делимости последовательными простыми числами, по одному простому числу за раз. Это не сито Эратосфена, но его часто путают с ним, хотя сито Эратосфена непосредственно генерирует композиты, а не проверяет их. Пробное деление имеет худшую теоретическую сложность, чем решето Эратосфена при генерации диапазонов простых чисел. ^[2]

При проверке каждого простого числа алгоритм оптимального пробного деления использует все простые числа, не превышающие его квадратный корень, тогда как сито Эратосфена производит каждую композицию только из ее простых множителей и получает простые числа «бесплатно» между композициями. Широко известный код функционального сита 1975 года Дэвида Тернера ^[12] часто представляется как пример сита Эратосфена ^[6], но на самом деле это неоптимальное сито пробного деления. ^[2]

Вычислительный анализ [ править ]

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

Работа, выполняемая этим алгоритмом, почти полностью состоит из операций по выбору представлений составных чисел, которые для базовой неоптимизированной версии представляют собой сумму диапазона, деленного на каждое из простых чисел до этого диапазона или

{\ displaystyle n \ sum _ {p \ leq n} {\ frac {1} {p}},}

где $n$ - диапазон рассева в этом и во всех последующих анализах.

По перегруппировкам второй теоремы Мертенса , это равно $п (лог - лог н + М)$ , как $п$ приближается к бесконечности, где М является постоянной Meissel-Мертенс примерно0,261 49 ...

Оптимизация, начинающаяся с квадрата каждого простого числа и отбраковка только для простых чисел, меньших квадратного корня, изменяет " $n$ " в приведенном выше выражении на $\sqrt n$ (или $n 1 / 2$ ) и не отбраковывать до тех пор, пока квадрат не означает, что сумма базовых простых чисел за вычетом двух вычитается из операций. Поскольку сумма первых $x$ простых чисел равна $1 / 2 x 2 log x$ ^[13], а теорема о простых числах утверждает, что $x$ приблизительно $Икс / журнал x$ , то сумма простых чисел до $n$ равна $п 2 / 2 журнала n$ , поэтому сумма базовых простых чисел до $\sqrt n$ равна $1 / журнал n$ выражается как коэффициент $n$ . Дополнительное смещение двух на базовое простое число равно $2 π (\sqrt n)$ , где $π$ - функция подсчета простых чисел в данном случае, или $4 \sqrt п / журнал n$ ; выражая это как множитель $n,$ как и другие термины, это $4 / \sqrt n войти n$ . Объединив все это, выражение для количества оптимизированных операций без факторизации колеса имеет вид

{\ displaystyle \ log \ log n - {\ frac {1} {\ log n}} \ left (1 - {\ frac {4} {\ sqrt {n}}} \ right) + M- \ log 2. }

Для случаев факторизации колес существует дополнительное смещение операций, которые не были выполнены.

{\ displaystyle \ sum _ {p \ leq x} {\ frac {1} {p}}}

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

{\ displaystyle \ prod _ {p \ leq x} p}

и легко определить, что этот коэффициент колеса равен

{\ displaystyle \ prod _ {p \ leq x} {\ frac {p-1} {p}}}

в виде $п - 1 / п$ - это доля оставшихся кандидатов на высшее простое число колеса, $x$ , и каждое последующее меньшее простое число оставляет соответствующую долю предыдущей объединенной дроби.

Комбинируя весь вышеприведенный анализ, общее количество операций для диапазона рассева до $n,$ включая факторизацию колес для простых чисел до $x,$ составляет приблизительно

{\ displaystyle \ prod _ {p \ leq x} {\ frac {p-1} {p}} \ left (\ log \ log n - {\ frac {1} {\ log n}} \ left (1- {\ frac {4} {\ sqrt {n}}} \ right) + M- \ log 2- \ sum _ {p \ leq x} {\ frac {1} {p}} \ right)}

.

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

$п$	нет колеса		шансы		2/3/5 колеса		2/3/5/7 колеса		2/3/5/7/11/13/17/19 колесо
10 ³	1,4090	1,3745	0,4510	0,4372	0,1000	0,0909	0,0580	0,0453	0,0060	-
10 ⁴	1,6962	1,6844	0,5972	0,5922	0,1764	0,1736	0,1176	0,1161	0,0473	0,0391
10 ⁵	1,9299	1,9261	0,7148	0,7130	0,2388	0,2381	0,1719	0,1714	0,0799	0,0805
10 ⁶	2,1218	2,1220	0,8109	0,8110	0,2902	0,2903	0,2161	0,2162	0,1134	0,1140
10 ⁷	2,2850	2,2863	0,8925	0,8932	0,3337	0,3341	0,2534	0,2538	0,1419	0,1421
10 ⁸	2,4257	2,4276	0,9628	0,9638	0,3713	0,3718	0,2856	0,2860	0,1660	0,1662

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

Алгоритмическая сложность [ править ]

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

Битовая сложность алгоритма является $O (п (лог - п) (журнал журнал п))$ битовых операций с требованием памяти $O (п)$ . ^[15]

Обычно реализуемая сегментированная версия страницы имеет ту же операционную сложность $O (n log log n),$ что и несегментированная версия, но снижает требования к пространству до очень минимального размера страницы сегмента плюс память, необходимую для хранения базовых простых чисел меньше, чем квадратный корень из диапазона, используемого для отбора составных частей из последовательных сегментов страницы размером $O (\sqrt п / журнал n)$ .

Специальная (редко, если вообще реализуется) сегментированная версия решета Эратосфена с базовой оптимизацией, использует $O (n)$ операций и $O (\sqrt n журнал журнал n / журнал n)$ бит памяти. ^[16]^[17]^[18]

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

$п$	нет колеса			шансы			2/3/5 колеса			2/3/5/7 колеса			комбо колесо			2/3/5/7/11/13/17/19 колесо
10 ⁶	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
10 ⁷	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
10 ⁸	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
10 ⁹	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
10 ¹⁰	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
10 ¹¹	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
10 ¹²	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
10 ¹³	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
10 ¹⁴	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
10 ¹⁵	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
10 ¹⁶	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$ не очень точна даже для максимальных практических диапазонов около 10 ¹⁶ . Можно понять, почему это не совпадает, посмотрев на приведенный выше расчетный анализ и увидев, что в пределах этих практических пределов диапазона рассева существуют очень важные постоянные смещения, так что очень медленно растущий $log log n$ срок не становится достаточно большим, чтобы сделать эти термины несущественными до тех пор, пока диапазон рассева не приблизится к бесконечности - далеко за пределами любого практического диапазона рассева. В пределах этих практических диапазонов эти значительные постоянные смещения означают, что производительность сита Эратосфена намного лучше, чем можно было бы ожидать, просто используя оценки асимптотической временной сложности на значительную величину, но это также означает, что наклон производительности с увеличением диапазона круче, чем прогнозировалось, поскольку выгода от постоянных смещений становится немного менее значительной.

Следует также отметить, что при использовании вычисленных соотношений операций к диапазону сита оно должно быть меньше примерно 0,2587, чтобы быть быстрее, чем часто сравниваемое сито Аткина, если операции занимают примерно одинаковое время в тактовых циклах ЦП, что является разумным предположением для алгоритма одного огромного битового массива. Используя это предположение, сито Аткина быстрее, чем сито Эратосфена с максимальным разложением колес, только для диапазонов более 10 ¹³в этот момент огромному массиву ситовых буферов потребуется около четверти терабайта (около 250 гигабайт) оперативной памяти, даже если использовалась битовая упаковка. Анализ сегментированных версий страницы покажет, что предположение о том, что время одной операции остается неизменным между двумя алгоритмами, не выполняется для сегментации страниц и что сито операций Аткина становится медленнее, чем сито Эратосфена, с увеличением диапазона. Таким образом, с практической точки зрения, сито Эратосфена с максимальной колесной факторизацией быстрее, чем сито Аткина, хотя сито Аткина быстрее для меньшего количества факторизации колес.

Использование большой нотации O также не является правильным способом сравнения практических характеристик четных вариантов сита Эратосфена, поскольку оно игнорирует постоянные факторы и смещения, которые могут быть очень важны для практических диапазонов: вариант сита Эратосфена, известный как колесное сито Притчарда ^{[ 16]}^[17]^[18] имеет производительность $O (n)$ , но его базовая реализация требует либо алгоритма «один большой массив», который ограничивает его полезный диапазон объемом доступной памяти, иначе он должен быть сегментирован по страницам, чтобы уменьшить память использовать. При реализации с сегментацией страниц для экономии памяти базовый алгоритм по-прежнему требует около $O (п / журнал n)$ бит памяти (намного больше, чем требуется для базового сегментированного сита Эратосфена с использованием $O (\sqrt п / журнал n)$ бит памяти). Работа Притчарда снизила требования к памяти до предела, как описано выше в таблице, но стоимость является довольно большим постоянным коэффициентом от примерно трех до примерно трех четвертей диапазона сита из-за сложных вычислений, необходимых для этого. Как видно из приведенной выше таблицы для основного сита Эратосфена, даже несмотря на то, что получившееся колесное сито имеет $O (n)$ производительность и приемлемые требования к памяти, оно никогда не будет быстрее, чем базовое сито Eratosthenes с разумным колесом факторизации для любого практического диапазона просеивания примерно в два раза. Помимо этого, его довольно сложно реализовать, он редко реализуется на практике, потому что он все еще использует больше памяти, чем базовые реализации решета Эратосфена, описанные здесь, а также медленнее для практических диапазонов. Таким образом, это скорее интеллектуальное любопытство, чем что-то практическое.

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

Доказательство Эйлера формулы дзета-произведения содержит версию решета Эратосфена, в которой каждое составное число удаляется ровно один раз. ^[8] То же самое сита вновь и наблюдало принимать линейное время от Gries & Мишра (1978) . ^[19] Он тоже начинается со списка чисел от 2 до $n$ по порядку. На каждом шаге первый элемент идентифицируется как следующее простое число, умножается на каждый элемент списка (таким образом, начиная с самого себя), а результаты отмечаются в списке для последующего удаления. Затем исходный элемент и отмеченные элементы удаляются из рабочей последовательности, и процесс повторяется:

 [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$ простыми числами (см. Факторизацию колеса ), так что список начнется со следующего prime, и все числа в нем ниже квадрата его первого элемента также будут простыми.

Таким образом, при генерации ограниченной последовательности простых чисел, когда следующее идентифицированное простое число превышает квадратный корень из верхнего предела, все остальные числа в списке являются простыми. ^[8] В примере, приведенном выше, это достигается при идентификации 11 как следующего простого числа, что дает список всех простых чисел, меньших или равных 80.

Обратите внимание, что числа, которые будут отброшены на шаге, все еще используются при маркировке кратных на этом шаге, например, для кратных 3 это 3 × 3 = 9 , 3 × 5 = 15 , 3 × 7 = 21 , 3 × 9 = 27 , ..., 3 × 15 = 45 , ..., так что с этим нужно быть осторожным. ^[8]

См. Также [ править ]

Сито Сундарама
Сито Аткина
Теория сита

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

^ a b c Хорсли, преподобный Сэмюэл, FRS, « Κόσκινον Ερατοσθένους или« Решето Эратосфена ». Он описывает его метод нахождения всех простых чисел», Philosophical Transactions (1683–1775), Vol. 62. (1772), стр. 327–347 .
^ a b c d О'Нил, Мелисса Э., «Подлинное сито Эратосфена» , Журнал функционального программирования , опубликованный в Интернете издательством Cambridge University Press, 9 октября 2008 г. doi : 10.1017 / S0956796808007004 , стр. 10, 11 (содержит два добавочных решета в Haskell: основанная на приоритетах очередь О'Нила и основанная на списках Ричардом Бердом).
^ Hoche, Ричард , изд. (1866), Nicomachi Geraseni Pythagorei Introductionis arithmeticae libri II , Leipzig: BG Teubner, p. 31 год
↑ JC Morehead, «Расширение решета Эратосфена на арифметические прогрессии и приложения», Annals of Mathematics, Second Series 10 : 2 (1909), pp. 88–104 .
^ Clocksin, Уильям Ф., Кристофер С. Mellish, программирование на Прологе , 1984, с. 170. ISBN 3-540-11046-1 .
^ a b Рансимен, Колин (1997). «Функциональная жемчужина: сита с ленивым колесом и спирали простых чисел» (PDF) . Журнал функционального программирования . 7 (2): 219–225. DOI : 10.1017 / S0956796897002670 .
^ Седжвик, Роберт (1992). Алгоритмы на C ++ . Эддисон-Уэсли. ISBN 978-0-201-51059-1., п. 16.
^ a b c d e f g h Джонатан Соренсон, Введение в сита простых чисел , Технический отчет по компьютерным наукам № 909, Департамент компьютерных наук Университета Висконсин-Мэдисон, 2 января 1990 г. (использование оптимизации, начиная с квадратов, и, таким образом, используются только числа, квадрат которых ниже верхнего предела).
^ Crandall & Pomerance, Простые числа: вычислительная перспектива , второе издание, Springer: 2005, стр. 121–24.
^ Бэйс, Картер; Хадсон, Ричард Х. (1977). «Сегментированное решето Эратосфена и простых чисел в арифметических прогрессиях до 10 ¹² ». БИТ . 17 (2): 121–127. DOI : 10.1007 / BF01932283 . S2CID 122592488 .
^ Дж. Соренсон, "Простое решето псевдоквадратов" , Труды 7-го Международного симпозиума по алгоритмической теории чисел . (ANTS-VII, 2006).
^ Тернер, Дэвид А. Руководство по языку SASL. Tech. представитель CS / 75/1. Департамент вычислительных наук Университета Сент-Эндрюс 1975 г. (). Но смотри также Питер Хендерсон, Моррис, Джеймс младший, ленивый Evaluator, 1976 , где мы находим следующее , приписываемый П. Quarendon:; приоритет неясен.primes = sieve [2..]; sieve (p:nos) = p:sieve (remove (multsof p) nos); remove m = filter (not . m); multsof p n = rem n p==0primeswrt[x;l] = if car[l] mod x=0 then primeswrt[x;cdr[l]] else cons[car[l];primeswrt[x;cdr[l]]] ; primes[l] = cons[car[l];primes[primeswrt[car[l];cdr[l]]]] ; primes[integers[2]]
^ Э. Бах и Дж. Шаллит, § 2.7 в алгоритмической теории чисел , т. 1: Эффективные алгоритмы, MIT Press, Кембридж, Массачусетс, 1996.
Перейти ↑ Peng, TA (осень 1985). «Миллион простых чисел сквозь сито» . БАЙТ . С. 243–244 . Проверено 19 марта +2016 .
^ Причард, Пол, "Линейные сита простых чисел: генеалогическое древо", Sci. Comput. Программирование 9 : 1 (1987), стр. 17–35.
^ a b Пол Притчард, "Сублинейное аддитивное решето для нахождения простых чисел", Сообщения ACM 24 (1981), 18–23. Руководство по ремонту 600730
^ a b Пол Причард, Объяснение колесного сита, Acta Informatica 17 (1982), 477–485. Руководство по ремонту 685983
^ a b Пол Причард, «Быстрые компактные сита для простых чисел» (среди прочего), Journal of Algorithms 4 (1983), 332–344. Руководство по ремонту 729229
^ Грис, Дэвид ; Мисра, Джаядев (декабрь 1978 г.), «Алгоритм линейного сита для поиска простых чисел» (PDF) , Коммуникации ACM , 21 (12): 999–1003, DOI : 10.1145 / 359657.359660 , hdl : 1813/6407 , S2CID 11990373 .

Внешние ссылки [ править ]

primesieve - Очень быстрое высокооптимизированное C / C ++ сегментированное решето Эратосфена
Эратосфен, сито в Энциклопедии математики
Интерактивная страница JavaScript
Сито Эратосфена Джорджа Бека, Демонстрационный проект Вольфрама .
Сито Эратосфена в Хаскелле
Проиллюстрирован и объяснен алгоритм сита Эратосфена. Реализации Java и C ++.
Связанное сито, написанное на языке ассемблера x86
Быстро оптимизированное высокопараллельное сегментированное сито CUDA Эратосфена в C
SieveOfEratosthenesInManyProgrammingLanguages c2 wiki-страница
Искусство первичного просеивания Сито Эратосфена на языке C от 1998 года с хорошими функциями и объясненными алгоритмическими приемами.

[horsley-1] Хорсли, преподобный Сэмюэл, FRS, « Κόσκινον Ερατοσθένους или« Решето Эратосфена ». Он описывает его метод нахождения всех простых чисел», Philosophical Transactions (1683–1775), Vol. 62. (1772), стр. 327–347 .

[ONeill-2] О'Нил, Мелисса Э., «Подлинное сито Эратосфена» , Журнал функционального программирования , опубликованный в Интернете издательством Cambridge University Press, 9 октября 2008 г. doi : 10.1017 / S0956796808007004 , стр. 10, 11 (содержит два добавочных решета в Haskell: основанная на приоритетах очередь О'Нила и основанная на списках Ричардом Бердом).

[nicomachus-3] Hoche, Ричард , изд. (1866), Nicomachi Geraseni Pythagorei Introductionis arithmeticae libri II , Leipzig: BG Teubner, p. 31 год

[4] JC Morehead, «Расширение решета Эратосфена на арифметические прогрессии и приложения», Annals of Mathematics, Second Series 10 : 2 (1909), pp. 88–104 .

[5] Clocksin, Уильям Ф., Кристофер С. Mellish, программирование на Прологе , 1984, с. 170. ISBN 3-540-11046-1 .

[Runciman-6] Рансимен, Колин (1997). «Функциональная жемчужина: сита с ленивым колесом и спирали простых чисел» (PDF) . Журнал функционального программирования . 7 (2): 219–225. DOI : 10.1017 / S0956796897002670 .

[sedgewick-7] Седжвик, Роберт (1992). Алгоритмы на C ++ . Эддисон-Уэсли. ISBN 978-0-201-51059-1., п. 16.

[intro-8] Джонатан Соренсон, Введение в сита простых чисел , Технический отчет по компьютерным наукам № 909, Департамент компьютерных наук Университета Висконсин-Мэдисон, 2 января 1990 г. (использование оптимизации, начиная с квадратов, и, таким образом, используются только числа, квадрат которых ниже верхнего предела).

[9] Crandall & Pomerance, Простые числа: вычислительная перспектива , второе издание, Springer: 2005, стр. 121–24.

[10] Бэйс, Картер; Хадсон, Ричард Х. (1977). «Сегментированное решето Эратосфена и простых чисел в арифметических прогрессиях до 10 ¹² ». БИТ . 17 (2): 121–127. DOI : 10.1007 / BF01932283 . S2CID 122592488 .

[11] Дж. Соренсон, "Простое решето псевдоквадратов" , Труды 7-го Международного симпозиума по алгоритмической теории чисел . (ANTS-VII, 2006).

[12] Тернер, Дэвид А. Руководство по языку SASL. Tech. представитель CS / 75/1. Департамент вычислительных наук Университета Сент-Эндрюс 1975 г. (). Но смотри также Питер Хендерсон, Моррис, Джеймс младший, ленивый Evaluator, 1976 , где мы находим следующее , приписываемый П. Quarendon:; приоритет неясен.primes = sieve [2..]; sieve (p:nos) = p:sieve (remove (multsof p) nos); remove m = filter (not . m); multsof p n = rem n p==0primeswrt[x;l] = if car[l] mod x=0 then primeswrt[x;cdr[l]] else cons[car[l];primeswrt[x;cdr[l]]] ; primes[l] = cons[car[l];primes[primeswrt[car[l];cdr[l]]]] ; primes[integers[2]]

[13] Э. Бах и Дж. Шаллит, § 2.7 в алгоритмической теории чисел , т. 1: Эффективные алгоритмы, MIT Press, Кембридж, Массачусетс, 1996.

[peng1985fall-14] Перейти ↑ Peng, TA (осень 1985). «Миллион простых чисел сквозь сито» . БАЙТ . С. 243–244 . Проверено 19 марта +2016 .

[15] Причард, Пол, "Линейные сита простых чисел: генеалогическое древо", Sci. Comput. Программирование 9 : 1 (1987), стр. 17–35.

[Pritchard1-16] Пол Притчард, "Сублинейное аддитивное решето для нахождения простых чисел", Сообщения ACM 24 (1981), 18–23. Руководство по ремонту 600730

[Pritchard2-17] Пол Причард, Объяснение колесного сита, Acta Informatica 17 (1982), 477–485. Руководство по ремонту 685983

[Pritchard3-18] Пол Причард, «Быстрые компактные сита для простых чисел» (среди прочего), Journal of Algorithms 4 (1983), 332–344. Руководство по ремонту 729229

[19] Грис, Дэвид ; Мисра, Джаядев (декабрь 1978 г.), «Алгоритм линейного сита для поиска простых чисел» (PDF) , Коммуникации ACM , 21 (12): 999–1003, DOI : 10.1145 / 359657.359660 , hdl : 1813/6407 , S2CID 11990373 .

[1]

vтеТеоретико-числовые алгоритмы
Тесты на первичность	AKS Годовая процентная ставка Бэйли – PSW Эллиптическая кривая Pocklington Ферма Лукас Лукас – Лемер Лукас – Лемер – Ризель Теорема прота Пепина Квадратичный Фробениус Соловей-Штрассен Миллер – Рабин
Прайм-генерирующий	Сито Аткина Сито Эратосфена Сито Сундарама Факторизация колес
Целочисленная факторизация	Непрерывная дробь (CFRAC) Диксона Эллиптическая кривая Ленстры (ECM) Эйлера Ро Полларда п - 1 п + 1 Квадратное сито (QS) Сито общего числового поля (GNFS) Сито со специальным числовым полем (SNFS) Рациональное сито Ферма Квадратные формы Шанкса Судебное отделение Шора
Умножение	Древнеегипетский Длинный Карацуба Тоом – Кук Шёнхаге-Штрассен Фюрера
Евклидово деление	Двоичный Разбивка Фурье Гольдшмидт Ньютон-Рафсон Длинный короткий SRT
Дискретный логарифм	Бэби-степ гигантский шаг Поллард ро Кенгуру Полларда Pohlig – Hellman Расчет индекса Функциональное поле сито
Наибольший общий делитель	Двоичный Евклидово Расширенное евклидово Лемера
Модульный квадратный корень	Чиполла Поклингтона Тонелли-Шанкс Берлекамп
Другие алгоритмы	Чакравала Корнаккия Возведение в степень возведением в квадрат Целочисленный квадратный корень Целочисленное отношение ( LLL ) Модульное возведение в степень Редукция Монтгомери Schoof
Курсивом указано, что алгоритм предназначен для чисел специальной формы.