Простой способ определения простого числа

Алгоритм нахождения простых чисел

Оптимизация алгоритма нахождения простых чисел

2 3 5 7 11 13 17 19 23 29 31… $250.000…

Дело было давно, в университете, когда мы начали изучать язык программирования Pascal и домашним заданием стало создание алгоритма нахождения простых чисел.

Алгоритм был придуман и тутже реализован на изучаемом языке. Программа запрашивала у пользователя число N и искала все простые числа до N включительно. После первого успешного теста сразу же возникло непреодолимое желание ввести N = «много». Программа работала, но не так быстро как хотелось бы. Естественно, дело было в многочисленных проверках (порядка N*N/2), поэтому пришлось избавиться от лишних. В итоге получилось 5 похожих алгоритмов каждый из которых работал быстре предыдущего. Недавно захотелось их вспомнить и реализовать, но на этот раз на Python.

Итак, поехали. Первый алгоритм, ударивший в студенческую голову, продемонстрирован в Листинге 1.

Очень быстро понимаешь, что в подсчете делителей каждого числа нет никакой надобности и поэтому переменную k можно освободить от своих обязанностей. Действительно, если хотябы один делитель имеется, то число уже не простое. Смотрим Листинг 2.

Конструкция break позволяет нам завершить выполнение внутреннего цикла и перейти к следующей итерации внешнего.
Далее возникает вопрос: «а зачем делить на 4, если на 2 число не делится?». Приходим к выводу, что искать делители нужно только среди простых чисел не превышающих делимое. Наш алгоритм превращается в… см. Листинг 3.

А потом вспоминаем теорию чисел и понимаем, что переберать надо только числа, не превосходящие корня из искомого. К примеру, если число M имеет делитель pi, то имеется делитель qi, такой, что pi * qi = M. То есть, чтобы найти пару, достаточно найти меньшее. Среди всех пар, предполагаемая пара с максимальным наименьшим — это пара с равными pi и qi, то есть pi * pi = M => pi = sqrt(M). Смотрим Листинг 4.

Код из Листинга 4 при N=10000 выполняется примерно в 1000 раз быстрее, чем самый первый вариант. Есть еще один «ускоритель», проверять только те числа, которые заканчиваются на 1, 3, 7 или 9 (так как остальные очевидно делятся на 2 или 5). Наблюдаем Листинг 5.

В следствии незначительного изменения Листинга 5 получаем небольшую прибавку в скорости:

Итого: Программа из последнего листинга выполняется, примерно, в 1300 раз быстрее первоначального варианта.
Я не ставил перед собой задачи написать программу максимально быстро решающую данную задачу, это скорее демонстрация начинающим программистам того, что правильно составленный алгоритм играет далеко не последнюю роль в оптимизации Ваших программ.

P.S.
Благодаря замечаниям получаем Листинг 7:

при N=10000, поучаем время:
time 1 = 26.24
time 2 = 3.113
time 3 = 0.413
time 4 = 0.096
time 5 = 0.087
time 6 = 0.083
time 7 = 0.053

Результаты при n = 1 000 000:
time 7 = 7.088
time 8 = 1.143

Источник

Еще раз о поиске простых чисел

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

На снимке — скульптура абстрактного экспрессиониста Марка Ди Суверо «Решето Эратосфена», установленная в кампусе Стэнфорского университета

Введение

Напомним, что число называется простым, если оно имеет ровно два различных делителя: единицу и самого себя. Числа, имеющие большее число делителей, называются составными. Таким образом, если мы умеем раскладывать числа на множители, то мы умеем и проверять числа на простоту. Например, как-то так:
(Здесь и далее, если не оговорено иное, приводится 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 — натуральное число, которое не делится ни на какой полный квадрат. Тогда

1. если n представимо в виде 4k+1, то оно просто тогда и только тогда, когда число натуральных решений уравнения 4x 2 +y 2 = n нечетно.
2. если n представимо в виде 6k+1, то оно просто тогда и только тогда, когда число натуральных решений уравнения 3x 2 +y 2 = n нечетно.
3. если 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. В комментариях напомнили про решето Сундарама. К сожалению, оно является лишь математической диковинкой и всегда уступает либо решетам Эратосфена и Аткина, либо проверке перебором делителей.

Источник

Ищем простые числа до триллиона за тридцать минут

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

Сегодня я хотел бы поделиться с вами различными вариантами реализации поиска простых чисел на языке C#, начиная с классических алгоритмов — решета Эратосфена, Сундарама и Аткина, и кончая различными оптимизациями (сегментация, факторизация). Особый упор я делал на простоту: самый быстрый из алгоритмов, который мне удалось получить, содержит 120 строк кода и ищет простые числа до триллиона меньше, чем за 30 минут, а до миллиарда — меньше, чем за секунду (это далеко от производительности лучших из существующих библиотек по поиску простых чисел, но эти библиотеки обычно содержат свыше 4000 строк кода).
В заключение мы применим самую быструю реализацию для поиска максимального расстояния между двумя соседними простыми числами до триллиона. Прежде чем заходить под кат, я предлагаю вам попытаться угадать ответ. Для сравнения, для простых чисел до 100 максимальное растояние равно 8 (между соседними простыми числами 89 и 97), а до тысячи — 20 (между 887 и 907).

Весь исходный код можно найти на гитхабе.

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

Решето Эратосфена — самый простой и известный алгоритм для поиска простых чисел. Его суть состоит в следующем:

• Выписываем числа 2, 3, . N;
• Берем первое число в списке и вычеркиваем из списка все числа, кратные ему, начиная с : 4, 6, 8, .
• Берем следующее число в списке и вычеркиваем кратные ему 9, 15, .
• Продолжаем процедуру для каждого последующего числа из оставшихся в списке пока выполняется неравенство ; оставшиеся после этого в списке числа и будут простыми:

вычеркиваем кратные 2: [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, . ]
вычеркиваем кратные 3: [2, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, . ]
вычеркиваем кратные 5: [2, 3, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, . ]
и так далее.
Практическая реализация использует битовый массив длины N, с всеми битами изначально установленными в 1, и для каждого составного числа меняет соответствующий бит на 0.

Поскольку наша задача — сравнить между собой разные реализации поиска простых чисел, мы наследуем все варианты от интерфейса ISieve, имеющего только один метод:

Для перечисления простых чисел был выбран способ колбеков, а не более привычные для C# энумераторы, поскольку он на 10-40% быстрее. Этот интерфейс позволяет единообразно тестировать разные реализации и сравнивать их между собой; в частности, мы будем считать количество, сумму и хеш простых чисел до миллиарда:

Алгоритм: решето Эратосфена
Ищет простые числа до миллиарда: 12.6 секунд.

2. Решето Сундарама

После этого, для оставшихся в списке чисел , последовательность чисел будет представлять все нечетные простые числа до N.

вычеркиваем 1+j+2*1*j: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, . ]
вычеркиваем 2+j+2*2*j: [1, 2, 3, 5, 6, 8, 9, 11, 12, 14, 15, . ]
вычеркиваем 3+j+2*3*j: [1, 2, 3, 5, 6, 8, 9, 10, 11, 14, . 24, . ]
и так далее.
последовательность 2n+1: [3, 5, 7, 11, 13, 17, 19, . ]

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

Алгоритм: решето Сундарама
Ищет простые числа до миллиарда: 18 секунд.

3. Решето Аткина

В 2003 году два профессора математики из Иллинойского университета в Чикаго Артур Аткин и Даниэль Бернштейн опубликовали статью, описывающую принципиально новый алгоритм поиска простых чисел, опирающийся на методы алгебраической теории чисел. Этот алгоритм теперь известен как решето Аткина. Его основная идея состоит в том, что существуют квадратичные формы для определенных классов , имеющие нечетное количество решений только когда — либо простое, либо имеет делитель . Это позволяет с помощью квадратичных форм отсеять все составные числа, не делящиеся на квадрат простого числа, а потом способом, аналогичным решету Эратосфена, отсеять кратные квадратам простых чисел.

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

Практическая реализация рассматривает числа , не делящиеся на 2, 3, 5, и имеющие определенные остатки от деления на 60.

Этот алгоритм асимптотически быстрее, чем решето Эратосфена: против , но за счет большей сложности в практическом применении часто проигрывает решету Эратосфена при сравнимом количестве оптимизаций.

Алгоритм: решето Аткина

Ищет простые числа до миллиарда: 11.4 секунд.

4. Колёсная факторизация

Колёсная факторизация — вид оптимизации решета Эратосфена, позволяющий заранее исключить из рассмотрения числа, заведомо не являющиеся простыми. Например, любое простое число, большее 6, имеет остаток от деления на 6 либо 1, либо 5: или : при любых других остатках число будет делиться либо на 2, либо на 3. Аналогично, простое число, большее , может иметь только один из 8 остатков от деления на 30: . Еще одно преимущество оптимизации — уменьшение потребения памяти: вместо одного бита на число для решета Эратосфена или 0.5 бит на число для решета Сундарама, факторизация с базой требует примерно 0.27 бит на число, поскольку позволяет хранить 30 чисел в 8 битах. При аккуратном применении оптимизация позволяет ускорить просеивание в несколько раз, однако неоптимизированные варианты обычно работают медленно за счет большей сложности. В прошлой публикации я подробно описывал алгоритм, однако он не был оптимизирован по производительности, поэтому здесь я приведу более простой и эффективный вариант.

Алгоритм: (2,3,5)-факторизация
Ищет простые числа до миллиарда: 9.6 секунд.

5. Оптимизированное решето Эратосфена

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

Соответственно, нечетное число будет храниться в бите с номером . Кроме того, при просеивании чисел, кратных нечетным простым , мы можем пропускать четные числа и обрабатывать только нечетные числа

Эта оптимизация дает нам практически двукратный выигрыш в производительности, и, кроме того, требует 0.5 бита на натуральное число, как и решето Сундарама.

Алгоритм: Оптимизированное решето Эратосфена
Ищет простые числа до миллиарда: 6.6 секунд.

6. Оптимизированное решето Сундарама

то есть, оно делает в точности то же самое, что и оптимизированное решето Эратосфена, только вычисления производятся над индексами битов, а не над самими числами. Поэтому сразу становится видно различие: решето Эратосфена вычеркивает только числа, кратные простым, а решето Сундарама — кратные всем числам! Очевидная оптимизация решета Сундарама — обрабатывать только те числа , для которых — простое число:

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

Производительность, что не удивительно, совпадает с предыдущим алгоритмом:

Алгоритм: Оптимизированное решето Сундарама
Ищет простые числа до миллиарда: 6.5 секунд.

7. Сегментированное решето Эратосфена

Все предыдущие алгоритмы хранили весь результат в памяти, что ограничивает их применение небольшими диапазонами. Например, при поиске простых чисел до триллиона, решето Эратосфена будет требовать 120 гигабайт оперативной памяти; кроме того, его скорость будет деградировать, так как просеивание (вычеркивание составных чисел) бегает по всему массиву, не эффективно используя кеши процессора.

Чтобы обойти это ограничение, вспомним, что для нахождения простых чисел до нам достаточно вычеркнуть числа, кратные простым, не превосходящим . Это позволяет нам сначала найти простые числа до , а потом разбить отрезок на меньшие отрезки (сегменты), и в каждом вычеркнуть кратные простым по отдельности. Нахождение первого числа, кратного , в сегменте требует немного арифметики:

вычеркиваем кратные 2: [ 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90]
вычеркиваем кратные 3: [ 81, 83, 85, 87, 89]
вычеркиваем кратные 5: [83, 85, 89]
вычеркиваем кратные 7 (нет в интервале): [83, 89]
Этот подход называется сегментированное решето, и с его применением требования к памяти снижаются с до . На практике размер интервалов выбирают либо равным , либо зависящим от размера кеша процессора.

За счет лучшего использования кеша алгоритм работает быстрее обычного решета Эратосфена на тех же данных:

Алгоритм: Сегментированное решето Эратосфена
Ищет простые числа до миллиарда: 8.6 секунд.

8. Оптимизированное сегментированное решето

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

Полная реализация с небольшими дополнительными оптимизациями позволяет ускорить предыдущий алгоритм примерно на 20%

Алгоритм: Оптимизированное сегментированное решето
Ищет простые числа до миллиарда: 7.1 секунд.

9. Сегментированная факторизация с базой 2

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

Интересно, что основной цикл исключения составных чисел не изменился, разница только в инициализации массива PrimeMultiples и в преобразовании индекса битов в число по знакомой нам формуле .

Эта оптимизация ускоряет поиск простых чисел больще, чем вдвое:

Алгоритм: Сегментированная факторизация с базой 2
Ищет простые числа до миллиарда: 3.4 секунды.

10. Сегментированная (2,3)-факторизация

В предыдущей реализации мы исключили из рассмотрения числа, делящиеся на два; теперь исключим числа, делящиеся на 2 и 3. Тогда оставшиеся числа делятся на два класса: дающие 1 или 5 в остатке от деления на 6. Поэтому вместо одного битового массива используем два: PrimeMultiples_6kPlus1 и PrimeMultiples_6kPlus5; они будут хранить числа вида и для чисел, кратных , имеющих 1 или 5 в остатке от деления на 6. Дополнительные усилия нужны, чтобы найти первое число вида , имеющее нужный остаток от деления на 6, но это решается простым перебором .

Алгоритм: Сегментированная (2,3)-факторизация
Ищет простые числа до миллиарда: 2.6 секунды.

11. Сегментированная (2,3,5)-факторизация

Применим ту же идею для чисел, не делящихся на 2, 3 и 5. Тогда у нас будет не два битовых массива, а восемь, по одному на каждый остаток от деления на 30: . В остальном код не особо изменится, и даст нам еще небольшое ускорение.

Алгоритм: Сегментированная (2,3,5)-факторизация
Ищет простые числа до миллиарда: 2.3 секунды.

12. Оптимизированная сегментированная (2,3,5)-факторизация

Факторизация позволяет уменьшить количество чисел, которые мы вычеркиваем, но вычисление индекса байта и бита в битовом массиве (как при просеивании, так и при повторном проходе по массиву для перечисления простых чисел) все равно занимает большую часть времени. Поэтому воспользуемся уже знакомым нам трюком, пользуясь тем, что в факторизации с базой (2,3,5) восемь остатков: вместо восьми битовых массивов используем один массив байт, в котором каждый из восьми бит отвечает за свой остаток от деления на 30. Это позволит нам в массиве PrimeMultiples держать индекс байта, а индекс бита будет постоянным. Тогда внутренний цикл просеивания становится исключительно простым:

При таком подходе повторный проход по массиву уже занимает больше времени, поскольку требует больше битовых операций. Однако любой байт может принимать всего 256 вариантов, поэтому мы можем заранее вычислить все 256 комбинаций остатков, и вообще избавиться от битовых операций. Например:

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

Эта оптимизация ускоряет предыдущую реализацию больше, чем в два раза, позволяя найти простые числа до миллиарда меньше, чем за секунду!

Алгоритм: Оптимизированная сегментированная (2,3,5)-факторизация
Ищет простые числа до миллиарда: 0.93 секунды.

Максимальное расстояние между простыми числами до триллиона

Используя последнюю версию алгоритма, легко написать простой код, сканирующий простые числа до триллиона и ищущий максимальное расстояние между соседними простыми числами:

Результат работы программы:

Простые числа до 1,000,000,000,000
Время работы: 26 минут 30 секунд
Максимальное расстояние между простыми числами: 540
между 738,832,927,927 и 738,832,928,467

Лучшие библиотеки

Рассказ был бы не полон без сравнения с лучшими из существующих библиотек по поиску простых чисел.

Самая известная библиотека — primegen, основанная на сильно оптимизированном решете Аткина. Она написана на C самим Даниэлем Бернштейном (соавтором Аткина) 20 лет назад и оптимизирована под Пентиум, поэтому для эффективного ее использования требуется поменять размер буфера в файле conf-words:

На моем ноутбуке наилучшая производительность достигается при установке буфера 65536 байт. В библиотеку входит утилита primegaps, которая как раз и ищет максимальное расстояние между простыми числами. Время ее работы для простых чисел до триллиона — 19 минут.

Но на данный момент, пожалуй, самая быстрая библиотека — primesieve, написанная на c++ и включающая огромное количество оптимизаций, включая различные стратегии просеивания для маленьких, средних и больших простых чисел, автоматическое определение размера кешей процессора и многопоточность. На моем ноутбуке программа ищет простые числа до триллиона в 8 потоков за 70 секунд. Автор библиотеки Kim Walish подробно описывает оптимизации в коде, поэтому эта библиотека отлично подходит для изучения самых лучших на сегодняшний день оптимизаций и для практического применения.

Сводная таблица с результатами

Время поиска простых чисел до миллиарда, секунд.

Источник