Сито Эратосфена - Sieve of Eratosthenes

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

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

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

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

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

Обзор

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

Анонимный

Простое число является натуральное число , которое имеет ровно два различных натуральное число делителей : число 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$ .

Еще одно усовершенствование состоит в том, чтобы вначале перечислить только нечетные числа $(3, 5, ..., n)$ и считать с шагом $2 p$ от $p 2$ на шаге 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  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

Алгоритм и варианты

Псевдокод

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

algorithm Sieve of Eratosthenes is
    input: an integer n > 1.
    output: all prime numbers from 2 through n.

    let A be an array of Boolean values, indexed by integers 2 to n,
    initially all set to true.
    
    for i = 2, 3, 4, ..., not exceeding  $\sqrt n$  do
        if A[i] is true
            for j = i², i²+i, i²+2i, i²+3i, ..., not exceeding n do
                A[j] := false

    return all i such that A[i] is true.

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

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

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

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

Разделите диапазон от 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)$ , а временная сложность такая же, как у обычного решета.

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

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

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

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

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

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

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

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

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

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

Обычно реализуемая сегментированная версия страницы имеет ту же операционную сложность $O (n log log n),$ что и несегментированная версия, но снижает требования к пространству до минимального размера страницы сегмента плюс память, необходимую для хранения базовых простых чисел меньше, чем квадратный корень из диапазона, используемого для отбора составных частей из последовательных сегментов страницы размером $O (.mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num,.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0 0.1em}.mw-parser-output .sfrac .den{border-top:1px solid}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px} √ п/журнал n)$ .

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

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

Сито Эйлера

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

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

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

Смотрите также

использованная литература

внешние ссылки

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

Languages

In other projects