Войти
В математике решето Аткина - это современный алгоритм для поиска всех простых чисел до указанного целого числа. По сравнению с древним решетом Эратосфена, размечавшим кратные числа простых чисел, решето Аткина выполняет некоторую предварительную работу, а затем размечает квадраты, кратные квадратам простых чисел, таким образом достигая лучшей теоретической асимптотической сложности. Создан в 2003 году А. О.Л. Аткин и Дэниел Дж. Бернштейн.
В алгоритме:
Алгоритм:
Сложив вышеуказанные отношения операций вместе, вышеупомянутый алгоритм принимает постоянное отношение операций переворачивания / маркировки к диапазону просеивания примерно 0,2587171021...; Исходя из фактической реализации алгоритма, коэффициент составляет около 0,25 для диапазонов просеивания до 67.
Ниже приводится псевдокод, который объединяет алгоритмы Аткина 3.1, 3.2 и 3.3 с использованием объединенного набора «s» всех чисел по модулю 60, за исключением тех, которые кратны простым числам 2, 3 и 5, в соответствии с алгоритмами для простой версии алгоритма , который поддерживает дополнительную битовую упаковку колеса; хотя конкретно не упоминается в упомянутой статье, этот псевдокод устраняет некоторые очевидные комбинации нечетных / четных x / y, чтобы сократить вычисления, когда эти вычисления никогда не пройдут тесты по модулю (т.е. будут давать четные числа или кратные 3 или 5):
limit ← 1000000000 // произвольный предел поиска // набор позиций "попадания" колеса для колеса 2/3/5, прокрученного дважды согласно алгоритму Аткина s ← {1,7,11,13,17, 19,23,29,31,37,41,43,47,49,53,59} // Инициализируем сито с достаточным количеством колес, чтобы включить предел: для n ← 60 × w + x, где w ∈ {0,1,..., limit ÷ 60}, x ∈ s: is_prime (n) ← false // Вставьте простые числа-кандидаты: // целые числа, которые имеют нечетное количество // представлений определенными квадратичными формами. // Шаг алгоритма 3.1: для n ≤ limit, n ← 4x² + y², где x ∈ {1,2,...} и y ∈ {1,3,...} // все x нечетные y, если n mod 60 ∈ {1,13,17,29,37,41,49,53}: is_prime (n) ← ¬is_prime (n) // переключить состояние // Шаг алгоритма 3.2: для n ≤ limit, n ← 3x² + y², где x ∈ {1,3,...} и y ∈ {2,4,...} // только нечетные x, если n mod 60 ∈ {7,19,31,43}: // и даже y is_prime ( n) ← ¬is_prime (n) // переключить состояние // Шаг алгоритма 3.3: для n ≤ limit, n ← 3x²-y², где x ∈ {2,3,...} и y ∈ {x-1, x- 3,..., 1} // все четные / нечетные, если n mod 60 ∈ {11,23,47,59}: // нечетные / четные комбинации is_prime (n) ← ¬is_prime (n) // переключить состояние / / Удалите композиты путем просеивания, только для тех вхождений на колесе: для n² ≤ limit, n ← 60 × w + x, где w ∈ {0,1,...}, x ∈ s, n ≥ 7: if is_prime ( n): // n простое число, не кратные его квадрату; // этого достаточно, потому что композиты без квадратов не могут попасть в этот список при c ≤ limit, c ← n² × (60 × w + x), где w ∈ {0,1,...}, x ∈ s: is_prime (c) ← false // одна обработка для получения последовательного списка простых чисел до предела: вывод 2, 3, 5 для 7 ≤ n ≤ limit, n ← 60 × w + x, где w ∈ {0,1,...}, x ∈ s: if is_prime (n): output nЭтот псевдокод написан для ясности; хотя некоторые избыточные вычисления были устранены путем управления комбинациями нечетных / четных x / y, он по-прежнему тратит почти половину своих квадратичных вычислений на непродуктивные циклы, которые не проходят тесты по модулю, так что он не будет быстрее, чем эквивалентный колесо разложено на множители (2/3/5) сито Эратосфена. Чтобы повысить его эффективность, необходимо разработать метод, минимизирующий или устраняющий эти непродуктивные вычисления.
Алгоритм полностью игнорирует любые числа с остатком по модулю 60, который делится на два, три или пять, поскольку числа с остатком по модулю 60, делимым на одно из этих трех простых чисел, сами являются делится на это простое число.
Все числа n с остатком по модулю шестьдесят 1, 13, 17, 29, 37, 41, 49 или 53 имеют остаток по модулю четыре от 1. Эти числа являются простыми тогда и только тогда, когда число решений 4x + y = n нечетное, а число бесквадратное (доказано как теорема 6.1 из).
Все числа n с остатком по модулю шестьдесят 7, 19, 31 или 43 имеют остаток по модулю шесть, равный 1. Эти числа являются простыми тогда и только тогда, когда количество решений 3x + y = n равно нечетное и число бесквадратное (доказано как теорема 6.2 из).
Все числа n с остатком по модулю шестьдесят 11, 23, 47 или 59 имеют остаток по модулю двенадцать от 11. Эти числа являются простыми тогда и только тогда, когда количество решений 3x - y = n равно нечетное и число бесквадратное (доказано как теорема 6.3 из).
Ни одно из потенциальных простых чисел не делится на 2, 3 или 5, поэтому они не могут делиться на свои квадраты. Вот почему бесквадратные проверки не включают 2, 3 и 5.
Можно вычислить, что каждая из трех вышеуказанных операций квадратного уравнения имеет ряд операций, которые - постоянное отношение диапазона, когда диапазон стремится к бесконечности; а также операции выборки без простых квадратов могут быть описаны с помощью простой дзета-функции (2) с постоянными смещениями и множителями, поэтому она также является постоянным множителем диапазона, когда диапазон стремится к бесконечности. Следовательно, описанный выше алгоритм может вычислять простые числа до N с использованием операций O (N) только с O (N) битами памяти.
Сегментированная версия страницы, реализованная авторами, имеет те же операции O (N), но снижает требования к памяти до уровня, необходимого для базовых простых чисел ниже квадратного корня из диапазона O (N / log N) бит памяти плюс минимальный буфер страницы. Это немного лучшая производительность при тех же требованиях к памяти, что и у сегментированного страницы сита Эратосфена, которое использует O (N log log N) операций и те же O (N / log N) бит памяти плюс минимальную страницу буфер. Однако такое сито не превосходит сито Эратосфена с максимальной практичной факторизацией колеса (комбинация просеивающего колеса 2/3/5/7 и предварительной отбраковки композитов в буферах страниц сегмента с использованием 2/3/5/7 / 11/13/17/19), который, хотя и имеет немного больше операций, чем Сито Аткина для очень больших, но практичных диапазонов, имеет постоянный коэффициент меньшей сложности на операцию примерно в три раза при сравнении времени на операцию между алгоритмы, реализованные Бернштейном в тактовых циклах ЦП на операцию. Основная проблема со страничным сегментированным решетом Аткина - сложность реализации последовательностей отбраковки «без простых квадратов» из-за того, что интервал между отсеиваниями быстро растет далеко за пределы диапазона буфера страницы; время, затрачиваемое на эту операцию в реализации Бернштейна, быстро увеличивается во много раз по сравнению со временем, затрачиваемым на фактические вычисления квадратного уравнения, а это означает, что линейная сложность той части, которая в противном случае была бы совершенно незначительной, становится основным потребителем времени выполнения. Таким образом, даже несмотря на то, что оптимизированная реализация может снова достичь временной сложности O (n), этот постоянный коэффициент увеличения времени на одну операцию означает, что сито Аткина работает медленнее.
Специальная модифицированная вариация «перечисления точек решетки», которая не является приведенной выше версией Решета Аткина, теоретически может вычислять простые числа до N, используя O (N / log log N) операций с N бит памяти, но этот вариант реализуется редко. Это немного лучше по производительности при очень высоких затратах памяти по сравнению как с обычной страничной сегментированной версией, так и с эквивалентной, но редко реализуемой версией сита Эратосфена, которая использует O (N) операций и O (N (log log N) / log N) бит памяти.
Притчард заметил, что для колесных сит можно уменьшить потребление памяти при сохранении временной сложности Big O, но это обычно происходит за счет увеличения постоянного коэффициента для время на операцию из-за дополнительной сложности. Следовательно, эта специальная версия, вероятно, будет более полезной как интеллектуальное упражнение, чем практическое простое сито с уменьшенными реальными затратами времени для данного большого практического диапазона рассева.
