Вывести список простых чисел
Наиболее наивный подход к поиску простых чисел заключается в следующем. Будем брать по очереди натуральные числа n , начиная с двойки, и проверять их на простоту. Проверка на простоту заключается в следующем: перебирая числа k из диапазона от 2 до n − 1 , будем делить n на k с остатком. Если при каком-то k обнаружится нулевой остаток, значит, n делится на k нацело, и число n составное. Если же при делении обнаруживались только ненулевые остатки, значит, число простое; в этом случае выводим его на экран. Ясно, что, получив нулевой остаток (тем самым обнаружив, что n составное), следует отказаться от дальнейших проб на делимость.
Заметим, что все простые числа, за исключением двойки, нечётные. Если обработать особо случай n = 2 , то все последующие числа n можно перебирать с шагом 2 . Это даст приблизительно двукратное увеличение производительности программы.
Оптимизированный перебор делителей
Ещё одно улучшение возникает благодаря следующему утверждению: наименьший делитель составного числа n не превосходит n . Докажем это утверждение от противного. Пускай число k является наименьшим делителем n , причём k > n . Тогда n = k l , где l ∈ ℕ , причём l ⩽ n , то есть l также является делителем числа n , кроме того, меньшим, чем k , а это противоречит предположению. Всё это означает, что, перебирая потенциальные делители, можно оборвать перебор, когда k достигнет n : если до этого момента делителей не найдено, то их нет вообще. Кстати, при проверке на простоту числа 11 это наблюдение позволяет сократить перебор более чем в три раза, а для числа 1111111111111111111 — более чем в 1054092553 раза (оба числа — простые).
Перебор с запоминанием найденных простых чисел
Существенно сократить перебор возможных делителей можно, пожертвовав памятью во время исполнения программы. В основе этой оптимизации лежит следующее утверждение: наименьший собственный делитель k составного числа n (то есть отличный от единицы и от самого n ) является простым. Докажите самостоятельно.
Поскольку при проверке числа n на простоту важен именно наименьший собственный делитель, делители следует искать среди простых чисел, перебирая их по порядку. Но где взять их список? Ответ прост: поскольку наша программа будет искать все простые числа по порядку, кроме вывода на экран будем добавлять их в список найденных простых. Для очередного n будем перебирать потенциальные делители только из этого списка, по-прежнему, вплоть до n .
Издержкой этого подхода является необходимость держать в памяти растущий список найденных простых чисел. Однако объём требуемой для этого памяти будет невелик по сравнению с громадным выигрышем в быстродействии. Следующая таблица даёт представление об экономии при переборе и о затратах памяти:
| n | количество k ⩽ n | количество простых k ⩽ n |
|---|---|---|
| 10 | 3 | 1 |
| 100 | 10 | 4 |
| 1000 | 31 | 10 |
| 10000 | 100 | 25 |
| 100000 | 316 | 65 |
| 1000000 | 1000 | 168 |
Решето Эратосфена
Другой алгоритм поиска простых чисел приписывают древнегреческому учёному Эратосфену Киренскому (Έρατοσθένης).
Обратите внимание: количество зачёркиваний у составного числа — это количество простых делителей (без учёта кратности).
Колёсный метод
Трюк, упомянутый в разделе «Наивный перебор», позволяет вдвое сократить список кандидатов в простые числа — заведомо составными будут все чётные числа кроме двойки. Посмотрим, нельзя ли подобным образом учесть ещё несколько первых простых чисел, чтобы дополнительно уменьшить число кандидатов.
Чисел, делящихся на 2 — половина, а делящихся на 3 — треть. Значит, доля чисел, делящихся хотя бы на одно из этих чисел, равна 1 2 + 1 3 − 1 2 ⋅ 1 3 = 2 3 (вычитается доля чисел, делящихся и на 2 , и на 3 , иначе такие числа будут учтены дважды). Для интересной операции, которую мы только что выполнили над дробями 1 2 и 1 3 , введём обозначение: x ⊕ y = x + y − x y .
Очевидно, операция ⊕ коммутативна: x ⊕ y = y ⊕ x . Кроме того, как нетрудно проверить, она ассоциативна: x ⊕ y ⊕ z = x ⊕ y ⊕ z .
Теперь ясно, что учёт следующего простого числа, пятёрки, увеличивает долю заведомо составных чисел (делящихся на 2 , 3 , 5 ) до 1 2 ⊕ 1 3 ⊕ 1 5 = 11 15 . Учёт семёрки даст 1 2 ⊕ 1 3 ⊕ 1 5 ⊕ 1 7 = 11 15 ⊕ 1 7 = 27 35 . Интересно выяснить, какую выгоду можно получить, учитывая следующие простые числа, и каковы будут издержки.
Мы вычислили «суммы» обратных величин для первых k простых чисел и свели результаты в таблицу:
| k | 1 2 ⊕ 1 3 ⊕ 1 5 ⊕ … ⊕ 1 p k |
|---|---|
| 1 | 0,5000… |
| 2 | 0,6667… |
| 3 | 0,7333… |
| 4 | 0,7714… |
| 5 | 0,7922… |
| 6 | 0,8082… |
| 7 | 0,8195… |
| 8 | 0,8290… |
| 9 | 0,8364… |
| 10 | 0,8421… |
Числа в правой колонке таблицы растут, но всё медленней.
Список чисел от 1 до P k , взаимно простых с P k , назовём колесом, а сами такие числа — спицами в колесе. Теперь мы знаем, что любое из простых чисел либо одно из p 1 , p 2 , … , p k , либо содержится среди чисел вида s + n P k , где s — спица. Все остальные натуральные числа, кроме единицы, заведомо составные, и их доля, как показывает таблица, довольно велика даже для небольших k .
Для проверки числа N на простоту следует прежде всего поискать N среди чисел p 1 , p 2 , … , p k . Если поиск не увенчался успехом, проверяем по очереди, не делится ли N на одно из p i . Если делится, число N — составное. Если же нет, ищем делители N среди спиц колеса s (пропустив, естественно, единицу), затем среди чисел вида s + P k , затем среди чисел вида s + 2 P k , затем — s + 3 P k , и так продолжаем до тех пор, пока квадрат очередного делителя не превысит N .
Построим колёса для первого одного простого числа, первых двух и первых трёх:
| k | колесо |
|---|---|
| 1 | 1 |
| 2 | 1 , 5 |
| 3 | 1 , 7 , 11 , 13 , 17 , 19 , 23 , 29 |
| 4 | 1 , 11 , 13 , 17 , 19 , 23 , 29 , 31 , 37 , 41 , 43 , 47 , 53 , 59 , 61 , 67 , 71 , 73 , 79 , 83 , 89 , 97 , 101 , 103 , 107 , 109 , 113 , 121 , 127 , 131 , 137 , 139 , 143 , 149 , 151 , 157 , 163 , 167 , 169 , 173 , 179 , 181 , 187 , 191 , 193 , 197 , 199 , 209 |
Возьмём для примера колесо, построенное для двух первых простых чисел — 2 и 3 . Проверяя на простоту число N при помощи такого колеса, убедившись, что N не двойка и не тройка, пытаемся делить это число сначала на 2 , 3 , а затем — на 5 , 7 , 11 , 13 , 17 , 19 , 23 , 25 , 29 , … , то есть на числа из арифметических прогрессий 1 + 6 t и 5 + 6 t , t = 0 1 2 3 … . При N = 661 имеет смысл остановиться на числе 25 , поскольку квадрат следующего в списке, 29 , уже больше 661 . Теперь можно заключить, что число 661 — простое.
Удобно изображать список возможных делителей в виде таблицы шириной P k (в нашем примере это 2 ⋅ 3 = 6 ): 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 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 … Серые числа заведомо составные. Среди цветных чисел также могут встретиться, хоть и редко, составные числа (синие) — мы помним, что колёсный метод исключает не все составные числа из рассмотрения.
Для проверки того же числа 661 на колесе, построенном для трёх первых простых чисел, нужно проверить его делимость сначала на 2 , 3 , 5 , затем — на 7 , 11 , 13 , 17 , 19 , 23 .
Есть соблазн использовать для построения колеса как можно больше первых простых чисел. Но не стоит этого делать. Выигрыш с добавлением очередного простого числа будет всё меньше и меньше, а количество спиц в k -ом колесе будет расти всё быстрее и быстрее. Можно показать, что количество спиц в k -ом колесе равно p 1 − 1 p 2 − 1 p 3 − 1 ⋅ … ⋅ p k − 1 . Эта последовательность выглядит так: 1 , 2 , 8 , 48 , 480 , 5760 , 92160 , 1658880 , … . Слишком большие колёса только замедлят выполнение программы, к тому же создание списка спиц потребует массу времени. Наши эксперименты показали, что оптимальное количество простых, используемых для построения колеса, равно четырём.
Ах, да. Почему метод называется колёсным? Возьмём колесо со спицами, пронумерованными от 1 до P k , и удалим спицы с номерами, не взаимно простыми с P k . Если прокатить такое колесо по прямой, отмечая следы концов уцелевших спиц, на прямой останутся отметки, принадлежащие арифметическим прогрессиям вида s + P k t . Первые три колеса показаны на рисунке 14.1. «Колёса для проверки чисел на простоту». Следующее колесо уже в семь раз больше самого крупного из показанных, и мы решили воздержаться от его рисования.
Источник
Еще раз о поиске простых чисел
В заметке обсуждаются алгоритмы решета для поиска простых чисел. Мы подробно рассмотрим классическое решето Эратосфена, особенности его реализации на популярных языках программирования, параллелизацию и оптимизацию, а затем опишем более современное и быстрое решето Аткина. Если материал о решете Эратосфена предназначен в первую очередь уберечь новичков от регулярного хождения по граблям, то алгоритм решета Аткина ранее на Хабрахабре не описывался.
На снимке — скульптура абстрактного экспрессиониста Марка Ди Суверо «Решето Эратосфена», установленная в кампусе Стэнфорского университета
Введение
Напомним, что число называется простым, если оно имеет ровно два различных делителя: единицу и самого себя. Числа, имеющие большее число делителей, называются составными. Таким образом, если мы умеем раскладывать числа на множители, то мы умеем и проверять числа на простоту. Например, как-то так:
(Здесь и далее, если не оговорено иное, приводится JavaScript-подобный псевдокод)
Время работы такого теста, очевидно, есть O(n ½ ), т. е. растет экспоненциально относительно битовой длины n. Этот тест называется проверкой перебором делителей.
Довольно неожиданно, что существует ряд способов проверить простоту числа, не находя его делителей. Если полиномиальный алгоритм разложения на множители пока остается недостижимой мечтой (на чем и основана стойкость шифрования RSA), то разработанный в 2004 году тест на простоту AKS [1] отрабатывает за полиномиальное время. С различными эффективными тестами на простоту можно ознакомиться по [2].
Если теперь нам нужно найти все простые на достаточно широком интервале, то первым побуждением, наверное, будет протестировать каждое число из интервала индивидуально. К счастью, если у нас достаточно памяти, можно использовать более быстрые (и простые) алгоритмы решета. В этой статье мы обсудим два из них: классическое решето Эратосфена, известное еще древним грекам, и решето Аткина, наиболее совершенный современный алгоритм этого семейства.
Решето Эратосфена
Древнегреческий математик Эратосфен предложил следующий алгоритм для нахождения всех простых, не превосходящих данного числа n. Возьмем массив S длины n и заполним его единицами (пометим как невычеркнутые). Теперь будем последовательно просматривать элементы S[k], начиная с k = 2. Если S[k] = 1, то заполним нулями (вычеркнем или высеем) все последующие ячейки, номера которых кратны k. В результате получим массив, в котором ячейки содержат 1 тогда и только тогда, когда номер ячейки — простое число.
Много времени можно сэкономить, если заметить, что, поскольку у составного числа, меньшего n, по крайней мере один из делителей не превосходит , процесс высевания достаточно закончить на 
. Вот анимация решета Эратосфена, взятая с Википедии:
Еще немного операций можно сэкономить, если — по той же причине — начинать вычеркивать кратные k, начиная не с 2k, а с номера k 2 .
Реализация примет следующий вид:
Эффективность решета Эратосфена вызвана крайней простотой внутреннего цикла: он не содержит условных переходов, а также «тяжелых» операций вроде деления и умножения.
Оценим сложность алгоритма. Первое вычеркивание требует n/2 действий, второе — n/3, третье — n/5 и т. д. По формуле Мертенса
так что для решета Эратосфена потребуется O(n log log n) операций. Потребление памяти же составит O(n).
Оптимизация и параллелизация
Первую оптимизацию решета предложил сам Эратосфен: раз из всех четных чисел простым является только 2, то давайте сэкономим половину памяти и времени и будем выписывать и высеивать только нечетные числа. Реализация такой модификации алгоритма потребует лишь косметических изменений (код).
Более развитая оптимизация (т. н. wheel factorization) опирается на то, что все простые, кроме 2, 3 и 5, лежат в одной из восьми следующих арифметических прогрессий: 30k+1, 30k+7, 30k+11, 30k+13, 30k+17, 30k+19, 30k+23 и 30k+29. Чтобы найти все простые числа до n, вычислим предварительно (опять же при помощи решета) все простые до . Теперь составим восемь решет, в каждое из которых будут входить элементы соответствующей арифметической прогрессии, меньшие n, и высеем каждое из них в отдельном потоке. Все, можно пожинать плоды: мы не только понизили потребление памяти и нагрузку на процессор (в четыре раза по сравнению с базовым алгоритмом), но и распараллелили работу алгоритма.
Наращивая шаг прогрессии и количество решет (например, при шаге прогрессии 210 нам понадобится 48 решет, что сэкономит еще 4% ресурсов) параллельно росту n, удается увеличить скорость алгоритма в log log n раз.
Сегментация
Что же делать, если, несмотря на все наши ухищрения, оперативной памяти не хватает и алгоритм безбожно «свопится»? Можно заменить одно большое решето на последовательность маленьких ситечек и высевать каждое в отдельности. Как и выше, нам придется предварительно подготовить список простых до , что займет O(n ½-ε ) дополнительной памяти. Простые же, найденные в процессе высевание ситечек, нам хранить не нужно — будем сразу отдавать их в выходной поток.
Не надо делать ситечки слишком маленькими, меньше тех же O(n ½-ε ) элементов. Так вы ничего не выиграете в асимптотике потребления памяти, но из-за накладных расходов начнете все сильнее терять в производительности.
Решето Эратосфена и однострочники
На Хабрахабре ранее публиковалась большая подборка алгоритмов Эратосфена в одну строчку на разных языках программирования (однострочники №10). Интересно, что все они на самом деле решетом Эратосфена не являются и реализуют намного более медленные алгоритмы.
Дело в том, что фильтрация множества по условию (например, на Ruby) или использование генераторных списков aka list comprehensions (например, на Haskell) вызывают как раз то, избежать чего призван алгоритм решета, а именно поэлементную проверку делимости. В результате сложность алгоритма возрастает по крайней мере до (это число фильтраций), умноженного на (минимальное число элементов фильтруемого множества), где — число простых, не превосходящих n, т. е. до O(n 3/2-ε ) действий.
Однострочник на Scala ближе к алгоритму Эратосфена тем, что избегает проверки на делимость. Однако сложность построения разности множеств пропорциональна размеру большего из них, так что в результате получаются те же O(n 3/2-ε ) операций.
Вообще решето Эратосфена тяжело эффективно реализовать в рамках функциональной парадигмы неизменяемых переменных. В случае, если функциональный язык (например, OСaml) позволяет, стоит нарушить нормы и завести изменяемый массив. В [3] обсуждается, как грамотно реализовать решето Эратосфена на Haskell при помощи техники ленивых вычеркиваний.
Решето Эратосфена и PHP
Запишем алгоритм Эратосфена на PHP. Получится примерно следующее:
Вторая проблема: массивы в PHP ужасны по накладным расходам памяти. У меня на 64-битной системе каждый элемент $S из кода выше съедает по 128 байт. Как обсуждалось выше, необязательно держать сразу все решето в памяти, можно обрабатывать его порционно, но все равно такие расходы дóлжно признать недопустимыми.
Для решения этих проблем достаточно выбрать более подходящий тип данных — строку!
Теперь каждый элемент занимает ровно 1 байт, а время работы уменьшилось примерно втрое. Скрипт для измерения скорости.
Решето Аткина
В 1999 году Аткин и Бернштейн предложили новый метод высеивания составных чисел, получивший название решета Аткина. Он основан на следующей теореме.
Теорема. Пусть n — натуральное число, которое не делится ни на какой полный квадрат. Тогда
- если n представимо в виде 4k+1, то оно просто тогда и только тогда, когда число натуральных решений уравнения 4x 2 +y 2 = n нечетно.
- если n представимо в виде 6k+1, то оно просто тогда и только тогда, когда число натуральных решений уравнения 3x 2 +y 2 = n нечетно.
- если n представимо в виде 12k-1, то оно просто тогда и только тогда, когда число натуральных решений уравнения 3x 2 −y 2 = n, для которых x >y, нечетно.
C доказательством можно ознакомиться в [4].
Из элементарной теории чисел следует, что все простые, большие 3, имеют вид 12k+1 (случай 1), 12k+5 (снова 1), 12k+7 (случай 2) или 12k+11 (случай 3).
Для инициализации алгоритма заполним решето S нулями. Теперь для каждой пары (x, y), где , инкрементируем значения в ячейках S[4x 2 +y 2 ], S[3x 2 +y 2 ], а также, если x > y, то и в S[3x 2 −y 2 ]. В конце вычислений номера ячеек вида 6k±1, содержащие нечетные числа, — это или простые, или делятся на квадраты простых.
В качестве заключительного этапа пройдемся по предположительно простым номерам последовательно и вычеркнем кратные их квадратам.
Из описания видно, что сложность решета Аткина пропорциональна n, а не n log log n как у алгоритма Эратосфена.
Авторская, оптимизированная реализация на Си представлена в виде primegen, упрощенная версия — в Википедии. На Хабрахабре публиковалось решето Аткина на C#.
Как и в решете Эратосфена, при помощи wheel factorization и сегментации, можно снизить асимптотическую сложность в log log n раз, а потребление памяти — до O(n ½+o(1) ).
О логарифме логарифма
На самом деле множитель log log n растет крайне. медленно. Например, log log 10 10000 ≈ 10. Поэтому с практической точки зрения его можно полагать константой, а сложность алгоритма Эратосфена — линейной. Если только поиск простых не является ключевой функцией в вашем проекте, можно использовать базовый вариант решета Эратосфена (разве что сэкономьте на четных числах) и не комплексовать по этому поводу. Однако при поиске простых на больших интервалах (от 2 32 ) игра стоит свеч, оптимизации и решето Аткина могут ощутимо повысить производительность.
P. S. В комментариях напомнили про решето Сундарама. К сожалению, оно является лишь математической диковинкой и всегда уступает либо решетам Эратосфена и Аткина, либо проверке перебором делителей.
Источник
