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

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

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

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

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

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

• 1 Обзор
  • 1.1 Пример
• 2 Алгоритм и варианты
  • 2.1 Псевдокод
  • 2.2 Сегментированное решето
  • 2.3 Инкрементальное решето
• 3 Вычислительный анализ
• 4 Алгоритмическая сложность
• 5 Решето Эйлера
• 6 См. также
• 7 Ссылки
• 8 Внешние ссылки

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

Анонимное

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

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

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

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

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

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

Пример

Чтобы найти все простые числа, меньшие или равные 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 45 67 89 1011 1213 1415 1617 1819 2021 2223 2425 2627 2829 30

Следующее число в списке после 2 - 3; зачеркните каждое третье число в списке после 3, считая от 3 с шагом 3 (это будут все числа, кратные 3 в списке):

2 3 45 67 891011 1213 14151617 1819 20212223 2425 26272829 30

Следующее число, еще не зачеркнутое в списке после 3, равно 5; вычеркните каждое 5-е число в списке после 5, считая от 5 с шагом 5 (т.е. все числа, кратные 5):

2 3 45 67 891011 1213 14151617 1819 20212223 242526272829 30

Следующее число, еще не зачеркнутое в списке после 5, - 7; следующим шагом будет вычеркнуть каждое седьмое число в списке после 7, но все они уже вычеркнуты на этом этапе, поскольку эти числа (14, 21, 28) также кратны меньшим простым числам, потому что 7 × 7 больше чем 30. Номера, не зачеркнутые в этом месте в списке, представляют собой все простые числа ниже 30:

2 3 5 7 11 13 17 19 23 29

Псевдокод

Решето Эратосфена может быть выражено в псевдокоде следующим образом:

алгоритм Сито Эратосфена isвход : целое число n>1. вывод : все простые числа от 2 до n. пусть A будет массивом Boolean значений, проиндексированных целым числом s от 2 до n, изначально все установлены на истина . для i = 2, 3, 4,..., не более √n doifA [i] isистиннодля j = i, i + i, i + 2i, i + 3i,..., не более n do A [j]: = falseвернуть все i такие, что A [ i] istrue .

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

Сегментированное сито

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

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

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

Если Δ выбрано равным √n, пространственная сложность алгоритма будет O (√n), а временная сложность такая же, как у обычного сита.

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

Инкрементное сито

Инкрементальная формулировка сита генерирует простые числа на неопределенный срок (т. е. без верхней границы) путем чередования генерации простых чисел с генерацией их кратных (так что pr imes можно найти в промежутках между кратными), где кратные каждого простого числа p генерируются непосредственно путем отсчета от квадрата простого числа с приращениями p (или 2p для нечетных простых чисел). Генерация должна запускаться только при достижении основного квадрата, чтобы избежать отрицательного воздействия на эффективность. Это может быть выражено символически в парадигме потока данных как

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

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

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

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

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

$n\; \sum \; p\; \le \; n\; 1\; p,\; \{\backslash \; displaystyle\; n\; \backslash \; sum\; \_\; \{p\; \backslash \; leq\; n\}\; \{\backslash \; frac\; \{1\}\; \{p\}\},\}$

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

Путем перестановки второй теоремы Мертенса это равно n (log log n + M), когда n приближается к бесконечности, где M - константа Мейсселя – Мертенса примерно 0,26149...

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

$журнал\; \; журнал\; \; n\; -\; 1\; журнал\; \; n\; (1-4\; n)\; +\; M\; -\; журнал\; \; 2.\; \{\backslash \; displaystyle\; \backslash \; log\; \backslash \; log\; n\; -\; \{\backslash \; frac\; \{1\}\; \{\backslash \; log\; n\}\}\; \backslash \; left\; (1\; -\; \{\backslash \; frac\; \{4\}\; \{\backslash \; sqrt\; \{n\}\}\}\; \backslash \; right)\; +\; M-\; \backslash \; log\; 2.\}$

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

$\sum \; p\; \le \; x\; 1\; p\; \{\backslash \; displaystyle\; \backslash \; sum\; \_\; \{p\; \backslash \; leq\; x\}\; \{\backslash \; frac\; \{1\}\; \{p\}\}\}$

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

$\prod \; p\; \le \; xp\; \{\backslash \; displaystyle\; \backslash \; prod\; \_\; \{p\; \backslash \; leq\; x\}\; p\}$

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

$\prod \; p\; \le \; xp\; -\; 1\; p\; \{\; \backslash \; displaystyle\; \backslash \; prod\; \_\; \{p\; \backslash \; leq\; x\}\; \{\backslash \; frac\; \{p-1\}\; \{p\}\}\}$

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

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

$\prod \; p\; \le \; xp\; -\; 1\; p\; (log\; \; log\; \; n\; -\; 1\; журнал\; \; N\; (1-4\; n)\; +\; M\; -\; журнал\; \; 2\; -\; \sum \; p\; \le \; x\; 1\; p)\; \{\backslash \; displaystyle\; \backslash \; prod\; \_\; \{p\; \backslash \; leq\; x\}\; \{\backslash \; frac\; \{p-1\}\; \{p\}\}\; \backslash \; left\; (\backslash \; log\; \backslash \; log\; n\; -\; \{\backslash \; frac\; \{1\}\; \{\backslash \; log\; n\}\}\; \backslash \; left\; (1\; -\; \{\backslash \; frac\; \{4\}\; \{\backslash \; sqrt\; \{n\}\}\}\; \backslash \; right)\; +\; M-\; \backslash \; log\; 2-\; \backslash \; sum\; \_\; \{p\; \backslash \; leq\; x\}\; \{\backslash \; frac\; \{1\}\; \{p\}\}\; \backslash \; right)\}$.

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

n	без колеса		шансы		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) и выше.

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

битовая сложность алгоритма составляет O (n (log n) (log log n)) битовые операции с требованиями к памяти of O (n).

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

Особо редко, если когда-либо, реализуемая сегментированная версия сито Эратосфена с базовой оптимизацией использует O (n) операций и O (√nlog log n / log n)бит памяти.

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

n	без колеса			шансы			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.04 6	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 также не является правильным способом для сравнения практических характеристик четных вариаций Сита Эратосфена, поскольку оно игнорирует постоянные коэффициенты и смещения, которые могут быть очень важны для практических диапазонов: Вариант сита Эратосфена, известный как сито с колесом Притчарда, имеет производительность O (n), но его базовая реализация требует либо алгоритма «один большой массив», который ограничивает его полезный диапазон объемом доступной памяти, иначе он должен быть сегментирован по страницам для уменьшения использования памяти. При реализации с сегментацией страниц для экономии памяти базовый алгоритм по-прежнему требует около O (n / log n)бит памяти (намного больше, чем требуется для базового сегментированного сита Эратосфена с использованием O (√n / log n)бит памяти). Работа Притчарда снизила требования к памяти до предела, как описано выше в таблице, но стоимость является довольно большим постоянным коэффициентом от трех до трех четвертей диапазона сита из-за сложных вычислений, необходимых для этого. Как видно из приведенной выше таблицы для базового сита Эратосфена, даже несмотря на то, что результирующее колесное сито имеет производительность O (n) и приемлемые требования к памяти, оно никогда не будет быстрее, чем базовое сито Эратосфена с разумной факторизацией колес для любого практического применения. диапазон просеивания примерно в два раза. Помимо этого, его довольно сложно реализовать, он редко реализуется на практике, потому что он все еще использует больше памяти, чем базовые реализации решета Эратосфена, описанные здесь, а также медленнее для практических диапазонов. Таким образом, это скорее интеллектуальное любопытство, чем что-то практическое.

Доказательство Эйлера формулы дзета-произведения содержит вариант решета Эратосфена, в котором каждое составное число удаляется ровно один раз. То же самое сито было обнаружено заново и наблюдалось линейное время Gries Misra (1978). Он также начинается со списка чисел от 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 простыми числами (см. разложение колеса ), так что список будет начните со следующего простого числа, и все числа в нем ниже квадрата его первого элемента также будут простыми.

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

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

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

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