stringtranslate.com

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

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

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

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

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

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

Обзор

Просеять двоек и просеять троек:
Решето Эратосфена.
Когда кратные возвышаются,
Числа, которые остаются, являются простыми.

Аноним [6]

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

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

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

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

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

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

Пример

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

 2 3 5 7 11 13 17 19 23 29

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

Псевдокод

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

Алгоритм Решето Эратосфена имеет  входные данные : целое число n > 1. выходные данные : все простые числа от 2 до n . пусть  A будет массивом булевых значений, индексированных целыми числами от s 2 до n , Изначально все установлено в значение true .  для  i = 2, 3, 4, ..., не превышающих √ n  do  if  A [ i ] is  true  для  j = i 2 , i 2 + i , i 2 +2 i , i 2 +3 i , ..., не превышающих n  do  set  A [ j ] := false вернуть все i, такие что A [ i ] является  истинным .

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

Сегментное сито

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

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

  1. Разделим диапазон от 2 до n на сегменты некоторого размера Δ ≤ √ n .
  2. Найдите простые числа в первом (т.е. самом нижнем) сегменте, используя обычное решето.
  3. Для каждого из следующих сегментов, в порядке возрастания, где m — самое высокое значение сегмента, найдите в нем простые числа следующим образом:
    1. Создайте логический массив размером Δ .
    2. Пометьте как непростые позиции в массиве, соответствующие кратным каждого простого числа p ≤ √ m, найденного на данный момент, перечислив его кратные с шагом p, начиная с наименьшего кратного p между m - Δ и m .
    3. Оставшиеся неотмеченные позиции в массиве соответствуют простым числам в сегменте. Нет необходимости отмечать какие-либо кратные этим простым числам, поскольку все эти простые числа больше √ m , так как для k ≥ 1 имеем .

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

Для диапазонов с верхним пределом n настолько большим, что просеивание простых чисел ниже √ n, требуемое сегментированным решетом Эратосфена, не может поместиться в памяти, вместо этого можно использовать более медленное, но гораздо более эффективное с точки зрения пространства сито, такое как псевдоквадратное простое решето, разработанное Джонатаном П. Соренсоном. [12]

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

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

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

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

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

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

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

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

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

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

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

Использование нотации big O игнорирует постоянные множители и смещения, которые могут быть очень значимыми для практических диапазонов: вариация решета Эратосфена, известная как решето Притчарда [16] [17] [18], имеет производительность O ( n ) , но ее базовая реализация требует либо алгоритма «одного большого массива», который ограничивает ее используемый диапазон объемом доступной памяти, либо ее необходимо сегментировать по страницам, чтобы сократить использование памяти. При реализации с сегментацией по страницам для экономии памяти базовый алгоритм все еще требует около O ( ⁠н/журнал n⁠ ) ​​бит памяти (гораздо больше, чем требуется для базового сегментированного решета страниц Эратосфена, использующего O ( ⁠√ н/журнал n⁠ ) ​​бит памяти). Работа Притчарда снизила требования к памяти за счет большого постоянного множителя. Хотя полученное колесо решета имеет производительность O ( n ) и приемлемые требования к памяти, оно не быстрее, чем разумно факторизованное колесо базовое решето Эратосфена для практических диапазонов просеивания.

решето Эйлера

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

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

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

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

Ссылки

  1. ^ abc Хорсли, преподобный Сэмюэл, FRS, « Κόσκινον Ερατοσθένους или Решето Эратосфена. Это отчет о его методе нахождения всех простых чисел», Philosophical Transactions (1683–1775), Vol. 62. (1772), стр. 327–347.
  2. ^ abcd O'Neill, Melissa E., «The Genuine Sieve of Eratosthenes», Journal of Functional Programming , опубликовано онлайн Cambridge University Press 9 октября 2008 г. doi :10.1017/S0956796808007004, стр. 10, 11 (содержит два инкрементных решета на Haskell: решето на основе очереди с приоритетами, разработанное O'Neill, и решето на основе списков, разработанное Richard Bird).
  3. ^ Хош, Ричард , изд. (1866), Никомахи Герасени Пифагорей «Введение в арифметику либри II», глава XIII, 3, Лейпциг: Б. Г. Тойбнер, стр. 30
  4. ^ ab Никомах из Герасы (1926), Введение в арифметику; переведено на английский Мартином Лютером Д'Уге; с исследованиями по греческой арифметике Фрэнка Эглстона Роббинса и Луиса Чарльза Карпински, глава XIII, 3 , Нью-Йорк: The Macmillan Company, стр. 204
  5. ↑ Дж. К. Морхед, «Расширение решета Эратосфена до арифметических прогрессий и приложений», Анналы математики, вторая серия 10:2 (1909), стр. 88–104.
  6. ^ Клоксин, Уильям Ф., Кристофер С. Меллиш, Программирование на Прологе , 1984, стр. 170. ISBN 3-540-11046-1 . 
  7. ^ ab Runciman, Colin (1997). "Functional Pearl: Ленивые колесные решета и спирали простых чисел" (PDF) . Журнал функционального программирования . 7 (2): 219–225. doi :10.1017/S0956796897002670. S2CID  2422563.
  8. ^ Седжвик, Роберт (1992). Алгоритмы в C++ . Эддисон-Уэсли. ISBN 978-0-201-51059-1., стр. 16.
  9. ^ abcdefgh Джонатан Соренсон, Введение в решето простых чисел, Технический отчет по компьютерным наукам № 909, Кафедра компьютерных наук Университета Висконсин-Мэдисон, 2 января 1990 г. (показано использование оптимизации, начинающейся с квадратов и, таким образом, использующей только те числа, квадрат которых меньше верхнего предела).
  10. ↑ Крэндалл и Померанс, Простые числа: вычислительная перспектива , второе издание, Springer: 2005, стр. 121–24.
  11. ^ Бэйс, Картер; Хадсон, Ричард Х. (1977). «Сегментированное решето Эратосфена и простые числа в арифметических прогрессиях до 10 12 ». BIT . 17 (2): 121–127. doi :10.1007/BF01932283. S2CID  122592488.
  12. ^ Дж. Соренсон, «Псевдоквадратичное простое решето», Труды 7-го Международного симпозиума по алгоритмической теории чисел . (ANTS-VII, 2006).
  13. ^ Тернер, Дэвид А. Руководство по языку SASL. Технический представитель CS/75/1. Кафедра вычислительной науки, Университет Сент-Эндрюс, 1975. ( ). Но см. также Питер Хендерсон, Моррис, Джеймс-младший, Ленивый оценщик, 1976, где мы находим следующее, приписываемое П. Кварендону: ; приоритет неясен.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]]
  14. ^ Пэн, ТА (осень 1985). «Миллион простых чисел через решето». BYTE . стр. 243–244 . Получено 19 марта 2016 г.
  15. ^ Притчард, Пол, «Линейные решета простых чисел: генеалогическое древо», Sci. Comput. Programming 9 :1 (1987), стр. 17–35.
  16. ^ ab Пол Притчард, «Сублинейное аддитивное решето для поиска простых чисел», Communications of the ACM 24 (1981), 18–23. MR 600730
  17. ^ Пол Притчард, Объяснение принципа работы решетчатого колеса, Acta Informatica 17 (1982), 477–485. MR 685983
  18. ^ ab Пол Притчард, «Быстрые компактные решета простых чисел» (среди прочих), Журнал алгоритмов 4 (1983), 332–344. MR 729229
  19. ^ Gries, David ; Misra, Jayadev (декабрь 1978), "Алгоритм линейного решета для поиска простых чисел" (PDF) , Communications of the ACM , 21 (12): 999–1003, doi :10.1145/359657.359660, hdl : 1813/6407 , S2CID  11990373.

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