Введение

Древний алгоритм для генерации простых чисел
скульптура

В математике, сито Эратосфена — это древний алгоритм для нахождения всех простых чисел до любого заданного предела. Оно работает путем итеративного исключения кратных каждого простого числа, начиная с первого простого числа, 2, и помечая их как составные (то есть, не простые). Кратные данного простого числа генерируются как последовательность чисел, начинающаяся с этого простого числа, с постоянной разностью между ними, равной этому простому числу. Это ключевое отличие сита от метода пробного деления, который последовательно проверяет каждое число-кандидат на делимость на каждое простое число. Ранний труд II века н.э. приписывает открытие Эратосфену Киренскому, греческому математику III века до н.э., хотя в нем описывается исключение нечетных чисел вместо простых. Являясь одним из множества алгоритмов для поиска простых чисел (сит), оно является одним из наиболее эффективных способов нахождения всех малых простых чисел. Его можно использовать для поиска простых чисел в арифметических прогрессиях.

Сито для увеличения

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

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

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