Эффективный способ поиска простых чисел
Наиболее наивный подход к поиску простых чисел заключается в следующем. Будем брать по очереди натуральные числа 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. «Колёса для проверки чисел на простоту». Следующее колесо уже в семь раз больше самого крупного из показанных, и мы решили воздержаться от его рисования.
Источник
Математик оптимизировал решето Эратосфена, чтобы искать простые числа с меньшим расходом памяти
38-летний перуанский математик Харальд Хельфготт три года назад доказал тернарную гипотезу Гольдбаха, а сейчас сумел оптимизировать компьютерный алгоритм для расчёта решета Эратосфена. Фото: Matías Loewy
В III в. до нашей эры древнегреческий математик, астроном, географ, филолог и поэт Эратосфен Киренский придумал гениальный способ поиска простых чисел. Очень эффективный и быстрый метод, который используется до сих пор, получил название решето Эратосфена.
Суть понятна из названия. Решето Эратосфена означает поиск простых чисел методом исключения. Берём список чисел, исключаем из него все составные числа — и получаем список простых чисел, словно просеяв список через решето.
В виде алгоритма решето Эратосфена формализуется следующим образом:
- Выписать подряд все целые числа от двух до n (2, 3, 4, …, n).
- Пусть переменная p изначально равна двум — первому простому числу.
- Зачеркнуть в списке числа от 2p до n считая шагами по p (это будут числа кратные p: 2p, 3p, 4p, …).
- Найти первое незачёркнутое число в списке, большее чем p, и присвоить значению переменной p это число.
- Повторять шаги 3 и 4, пока возможно.
После выполнения этой операции незачёркнутыми в списке остаются только простые числа.
Очевидно, что компьютерная реализация решета Эратосфена требует большого объёма памяти. Так оно и было, пока своё решение проблемы не предложил 38-летний перуанский математик Харальд Хельфготт.
Харальд Хельфготт
Харальд Хельфготт привлёк всеобщее внимание в 2013 году, когда ему удалось решить тернарную проблему Гольдбаха. Тернарная проблема Гольдбаха — более слабое утверждение основной бинарной проблемы Гольдбаха — одной из самых известных открытых математических проблем, которая до сих пор остаётся нерешённой. Это утверждение о том, что любое чётное число, начиная с 4, можно представить в виде суммы двух простых чисел.
Тернарная гипотеза Гольдбаха напрямую следует из бинарной гипотезы. Тернарная гипотеза утверждает, что любое нечётное число, начиная с 7, можно представить в виде суммы трёх простых чисел. Эта гипотеза была доказана для чисел от N до бесконечности Иваном Виноградовым в 1937 году, за что он получил Сталинскую премию и звание Героя Социалистического Труда. Советские математики думали, что Виноградов доказал гипотезу для всех чисел, но на самом деле позже выяснилось, что нижняя граница N в работе Виноградова составляет 10 6 846 168 .
Перуанский математик Харальд Хельфготт сумел окончательно доказать эту гипотезу, снизив границу N до приемлемого числа 10 29 , а все остальные числа проверили на суперкомпьютере. Его доказательство опубликовано в журнале Science 24 мая 2013 года (doi: 10.1126/science.340.6135.913). Оно подтверждено другими квалифицированными математиками, способными понять доказательство, например, Теренсом Тао.
Сейчас талантливый математик Харальд Хельфготт, чьи предки происходят из Черновицкой области, направил свои усилия на ещё одну важную задачу современной науки — оптимизацию поиска простых чисел. Ему удалось предложить улучшенный вариант решётки Эратосфена — метода поиска простых чисел, сформулированного примерно в 240 г до н.э. Новый вариант в компьютерной реализации требует меньше оперативной памяти, что означает меньший объём подкачки страниц из виртуальной памяти — следовательно, процесс существенно ускоряется.
«Как и многие другие 10-летние дети, я изучал решето Эратосфена в начальной школе», — говорит Харальд Хельфготт, который сейчас работает в Национальном центре научных исследований Франции и Гёттингенском университете.
Харальд признался, что начал думать «даже слишком много» о решётке Эратосфена ещё во время работы над тернарной проблемой Гольдбаха. В частности, об объёме данных в памяти. Он понимал, что именно ограниченный объём памяти является бутылочным горлышком, которое снижает максимально возможную скорость вычислений в данном случае.
Специалисты говорят, что эффективность алгоритма определяется двумя факторами:
- Количество операций на один бит входных данных.
- Количество бит в памяти во время выполнения инструкций.
По количеству операций на бит решётка Эратосфена относительно эффективна. Оно растёт пропорционально размеру интервала от 1 до N. А вот если посмотреть, что нужно хранить в памяти для каждого шага алгоритма на больших интервалах, то ни о какой эффективности не идёт и речи.
Оптимизация решета Эратосфена
Для оптимизации компьютерного алгоритма решета Эратосфена математик применил вариант того же метода, который использовал при работе над тернарной проблемой Гольдбаха. Речь идёт о круговом методе Харди-Литтлвуда. Том самом методе, который в начале прошлого века великолепно усовершенствовал математик Иван Виноградов, в результате чего почти сумел доказать гипотезу Гольдбаха.
Согласно методу Харди-Литтлвуда, решение задачи задаётся интегралом по единичной окружности от некоторого ряда. Этот интеграл разбивается на два, один из которых оценивается, а про другой доказывается его относительная малость. Составляющие первую сумму называются большими дугами, а вторую — малыми.
Сам математик объясняет метод следующим образом:
«Анализ количества решений производится, по сути, посредством преобразования Фурье. Представьте себе, что простые числа — это звуки на некоторой записи, скажем, в моменты времени 2, 3, 5, 7, 11 и так далее микросекунд. После преобразования у вас получается своего рода шум, в котором вы пытаетесь услышать какие-то ноты. Среди них есть такие, которые слышны достаточно хорошо, — это и есть большие дуги. А есть частоты, которые просто являются шумовыми фрагментами, — это малые дуги. Весь метод распадается на две части — выделение нот и доказательство того, что остальное на самом деле шум. За первую часть метода отвечают оценки на большие дуги, за второй — на малые».
На основе метода Харди-Литтлвуда учёный разработал подход, который позволяет вместо объёма оперативной памяти N использовать объём памяти ∛N (кубический корень из N).
Образно говоря, вместо 1 гигабайта памяти, т.е. 10 9 байт (не путать с гибибайтом 2 30 ) нужен всего лишь 1 килобайт (∛10 9 = 10 3 байт).
Гигабайт и килобайт — большая разница, согласитесь.
Такая оптимизация в каком-то смысле стала побочным эффектом решения проблемы Гольдбаха.
Тезисы своей работы Харальд Хельфготт представил на 21-м Латиноамериканском коллоквиуме по алгебре в Буэнос-Айресе 25-29 июля 2016 года, а также на мероприятии Sinapsis 2016 в Париже — неформальной встрече перуанских учёных, проживающих в Европе.
Есть разные алгоритмы для поиска простых чисел, но Хельфготт обращает внимание, что решето Эратосфена имеет важное качество — оно совместимо с другими математическими операциями, такими как факторизация, а ведь именно на факторизации (разложении больших чисел на простые множители) базируется криптография. «Факторизация стала ключевым элементом современной цивилизации», — констатирует Хельфготт.
Источник
