Проверить что число простое
Проверка числа на простоту
Простых чисел бесконечное множество. В интернете в свободном доступе можно найти таблицы простых чисел до 21 000 000. Существующие методы проверки чисел на простоту очень сложны, не универсальны, поэтому мной разработан еще один способ проверки числа на простоту для чисел больше 10.
Простое число – целое положительное число, которое имеет два различных натуральных делителя: единицу и самого себя, то есть, если число можно разложить на множители значит оно не простое – а составное.
Пусть А – натуральное число, тогда
где Х и Y – натуральные числа.
Мы знаем, что простые числа не четные, и все числа, заканчивающиеся на 5 и 0 кратны пяти, значит, простые числа всегда заканчиваются на 1, 3, 7, 9. Выберем из таблицы умножения примеры, в которых последняя цифра произведения равна 1 или 3 или 7 или 9 (смотрим рисунок).
Получаем, что бы последняя цифра числа А была равна 1 – последние цифры чисел Х и Y должны быть 1 и 1 (1х1=1) или 3 и 7 (3х7=21) или 9 и 9 (9х9=81).
Что бы последняя цифра числа А была равна 3 – последние цифры чисел Х и Y должны быть равны 1 и 3 (1х3=3) или 7 и 9 (7х9=63).
Что бы последняя цифра числа А была равна 7 – последние цифры чисел Х и Y должны быть равны 1 и 7 (1х7=7) или 3 и 9 (3х9=27).
Что бы последняя цифра числа А была равна 9 – последние цифры числе Х и Y должны быть равны 1 и 9 (1х9=9) или 3 и 3 (3х3=9) или 7 и 7 (7х7=49).
Рассмотрим каждую пару последних цифр для Х и Y по отдельности.
Мы получили уравнение с двумя переменными при известном А. Решений данного уравнения множество, но при условии, что х и у – натуральные, количество решений конечно, или вообще их нет в целочисленном выражении. Получается, если решений нет в натуральных числах, то А является простым числом.
Для остальных пар выполняем аналогичные действия и получаем:
Решение полученных уравнений при больших А – задача трудоемкая, поэтому была написана программа для определения простоты числа согласно нашим уравнениям.
Код написан на Visual Basic.
Данный макрос, написанный на Visual Basic, имеет ряд недостатков. Он ограничен вычислительными возможностями excel и при больших числах более 400млн для предположительно простых чисел выдает ошибку о переполнении. Но, для составных чисел, так как алгоритм после нахождения одного из возможных множителей дальше не считает, макрос считает большие числа. Время расчета в VB составляет 1-5 секунд. Так как расчетные уравнения рассчитаны для чисел больших 10, то простота чисел из первого десятка просто добавлена в макрос.
Таким образом, получен математический способ проверки числа на простоту и написан программный код в Visual Basic для его реализации. Но так как вычислительные возможности в Visual Basic ограничены, для проверки простоты больших чисел требуется написание программы на других языках программирования.
Алгоритм проверки на простоту за O (log N)
Проверка на простоту
Чтобы определить, является ли данное число N простым, безусловно, достаточно написать простой цикл поиска делителей числа N:
Данная функция проверки числа на простоту достаточно эффективна — асимптотика ее работы O (sqrt(N)). Однако, иногда в спортивном программировании нужно уметь проверять число на простоту быстрее.
В некоторых случаях, когда требуется выполнять такую проверку для чисел из некоторого диапазона, то целесообразно воспользоваться алгоритмом Решето Эратосфена.
В данной статье я рассмотрю другой способ выполнять единичные проверки на простоту — тест Ферма.
Вероятностный алгоритм за O (log N) с тестом Ферма
Математическое обоснование теста Ферма достаточно хорошо описано здесь.
Я же приведу его конкретную реализацию на C++, а также покажу, как бороться с переполнением типа long long при возведении в степень.
Тест Ферма
Для того, чтобы проверить число N на простоту с достаточно хорошей вероятностью безошибочности, достаточно 100 раз проверить случайное число A тестом Ферма:
Также стоит отметить, что числа A и N должны быть взаимно просты. Если это условие не выполняется, то число N — заведомо непростое.
Отмечу, что данная функция проверки использует функции нахождения НОД, а также быстрого возведения в степень по модулю.
Нахождение НОД
Собственно, в нахождении НОДа двух чисел проблем меньше всего. Воспользуемся алгоритмом Евклида:
Быстрое возведение в степень по модулю
Быстрое возведение в степень (бинарное) известно довольно широко. Отмечу только, что при перемножении двух чисел типа long long может произойти переполнение типа еще до того, как мы возьмем результат по модулю. Поэтому используем функцию двоичного умножения двух чисел также по модулю. Ее смысл очень похож на быстрое возведение в степень.
Точно также как и при возведении в степень, если второй множитель четный, то можно разделить его на 2, и перейти к вычислению произведения чисел A и B/2. Иначе, нужно вычислить произведение чисел A и B — 1.
Как определить простое число или нет
Простые числа – это числа, которые делятся только на себя и на 1; все остальные числа называются составными числами. Существует множество способов определения того, является ли число простым. Некоторые способы являются относительно простыми, но они не подходят для больших чисел. Другие способы, применимые для больших чисел, фактически представляют собой вероятностные алгоритмы, которые иногда ошибочно характеризуют число как простое или составное.
Метод 1 Перебор делителей
Перебор делителей – самый легкий способ определить простоту числа. В случае малых чисел это, пожалуй, также и самый быстрый способ. Он основан на определении простого числа: число является простым, если оно не имеет делителей кроме самого себя и единицы.
Метод 2 Тест Ферма
В 1640 году французский математик Пьер Ферма впервые сформулировал теорему (малая теорема Ферма), которая используется при определении простоты числа. Фактически, тест Ферма служит для определения составных чисел, а не простых. Этот тест с уверенностью определяет, является ли число составным, или определяет, что число «скорее всего» простое. Тест Ферма полезен в случаях, когда перебор делителей непрактичен и когда доступен список чисел, являющихся исключениями из теоремы.
Метод 3 Тест Миллера-Рабина
Тест Миллера-Рабина эффективно определяет, является ли число составным (и лучше обрабатывает исключения, такие как числа Кармайкла).
Условие задачи 2.30
Задача 2.30
Дан одномерный массив А, состоящий из натуральных чисел. Вывести на экран количество простых чисел в массиве.
Для начала напомню, что такое простые числа.
Простое число — это натуральное число, которое имеет ровно два различных натуральных делителя — единицу и самого себя.
То есть если число делится без остатка только на 1 и на самого себя, то такое число является простым.
Например, простыми числами являются 2, 3, 5 и т.п.
А вот 4 уже не является простым, так как делится без остатка не только на 1 и 4, но ещё и на 2.
Если вы подзабыли, что такое натуральное число, то см. здесь.
А теперь перейдём к задаче. По сути нам нужна программа, определяющая простые числа. А уж перебрать элементы массива в цикле и проверить их значения — это дело техники. Заодно мы можем не только подсчитать, но и вывести на экран простые числа массива.
Как определить простое число в Паскале
Алгоритм решения с подробным разбором приведу на Паскале. Решение на С++ можете посмотреть в примере программы на С++.
ВАЖНО!
На этом многие могут ошибиться. В определении сказано, что простое число имеет ровно два различных делителя. Следовательно, число 1 не является простым (также не является простым, так как ноль можно делить на любые числа).
Проверять, является ли число простым, будем с помощью функции, которую сами и создадим. Эта функция будет возвращать TRUE, если число простое.
В функции сначала будем проверять, не является ли число меньше двух. Если да, то это уже не простое число. Если же число равно 2 или 3, то оно является однозначно простым и делать какие-то дополнительные проверки не требуется.
А вот если число N будет больше трёх, то в этом случае в цикле будем перебирать все возможные делители, начиная от 2 до (N-1). Если на какой-то делитель число N делится без остатка, значит, это тоже не простое число. В этом случае мы прерываем цикл (потому что проверять дальше нет смысла), а функция возвращает FALSE.
Проверять, делится ли число на самоё себя нет смысла (поэтому цикл длится только до N-1).
Саму функцию здесь приводить не буду — посмотрите её в примерах программ.
В статье рассматриваются понятия простых и составных чисел. Даются определения таких чисел с примерами. Приводим доказательство того, что количество простых чисел неограниченно и произведем запись в таблицу простых чисел при помощи метода Эратосфена. Будут приведены доказательства того, является ли число простым или составным.
Простые и составные числа – определения и примеры
Простые и составные числа относят к целым положительным. Они обязательно должны быть больше единицы. Делители также подразделяют на простые и составные. Чтобы понимать понятие составных чисел, необходимо предварительно изучить понятия делителей и кратных.
Составными числами называют целые числа, которые больше единицы и имеют хотя бы три положительных делителя.
Единица не является ни простым ни составным числом. Она имеет только один положительный делитель, поэтому отличается от всех других положительных чисел. Все целые положительные числа называют натуральными, то есть используемые при счете.
Простые числа – это натуральные числа, имеющие только два положительных делителя.
Составное число – это натуральное число, имеющее более двух положительных делителей.
Натуральные числа, которые не являются простыми, называют составными.
Таблица простых чисел
Для того, чтобы было проще использовать простые числа, необходимо использовать таблицу:
Рассмотрим теорему, которая объясняет последнее утверждение.
Наименьший положительный и отличный от 1 делитель натурального числа, большего единицы, является простым числом.
Простых чисел бесконечно много.
Видно, что может быть найдено любое простое число среди любого количества заданных простых чисел. Отсюда следует, что простых чисел бесконечно много.
Решето Эратосфена
Данный способ неудобный и долгий. Таблицу составить можно, но придется потратить большое количество времени. Необходимо использовать признаки делимости, которые ускорят процесс нахождения делителей.
Перейдем к формулировке теоремы.
Данное число простое или составное?
Перед решением необходимо выяснять, является ли число простым или составным. Зачастую используются признаки делимости. Рассмотрим это на ниже приведенных примере.
Доказать что число 898989898989898989 является составным.
Ответ: 11723 является составным числом.
Еще раз о поиске простых чисел
В заметке обсуждаются алгоритмы решета для поиска простых чисел. Мы подробно рассмотрим классическое решето Эратосфена, особенности его реализации на популярных языках программирования, параллелизацию и оптимизацию, а затем опишем более современное и быстрое решето Аткина. Если материал о решете Эратосфена предназначен в первую очередь уберечь новичков от регулярного хождения по граблям, то алгоритм решета Аткина ранее на Хабрахабре не описывался.
На снимке — скульптура абстрактного экспрессиониста Марка Ди Суверо «Решето Эратосфена», установленная в кампусе Стэнфорского университета
Введение
Напомним, что число называется простым, если оно имеет ровно два различных делителя: единицу и самого себя. Числа, имеющие большее число делителей, называются составными. Таким образом, если мы умеем раскладывать числа на множители, то мы умеем и проверять числа на простоту. Например, как-то так:
(Здесь и далее, если не оговорено иное, приводится JavaScript-подобный псевдокод)
Время работы такого теста, очевидно, есть O(n ½ ), т. е. растет экспоненциально относительно битовой длины n. Этот тест называется проверкой перебором делителей.
Довольно неожиданно, что существует ряд способов проверить простоту числа, не находя его делителей. Если полиномиальный алгоритм разложения на множители пока остается недостижимой мечтой (на чем и основана стойкость шифрования RSA), то разработанный в 2004 году тест на простоту AKS [1] отрабатывает за полиномиальное время. С различными эффективными тестами на простоту можно ознакомиться по [2].
Если теперь нам нужно найти все простые на достаточно широком интервале, то первым побуждением, наверное, будет протестировать каждое число из интервала индивидуально. К счастью, если у нас достаточно памяти, можно использовать более быстрые (и простые) алгоритмы решета. В этой статье мы обсудим два из них: классическое решето Эратосфена, известное еще древним грекам, и решето Аткина, наиболее совершенный современный алгоритм этого семейства.
Решето Эратосфена
Древнегреческий математик Эратосфен предложил следующий алгоритм для нахождения всех простых, не превосходящих данного числа n. Возьмем массив S длины n и заполним его единицами (пометим как невычеркнутые). Теперь будем последовательно просматривать элементы S[k], начиная с k = 2. Если S[k] = 1, то заполним нулями (вычеркнем или высеем) все последующие ячейки, номера которых кратны k. В результате получим массив, в котором ячейки содержат 1 тогда и только тогда, когда номер ячейки — простое число.
Реализация примет следующий вид:
Эффективность решета Эратосфена вызвана крайней простотой внутреннего цикла: он не содержит условных переходов, а также «тяжелых» операций вроде деления и умножения.
Оценим сложность алгоритма. Первое вычеркивание требует n/2 действий, второе — n/3, третье — n/5 и т. д. По формуле Мертенса
так что для решета Эратосфена потребуется O(n log log n) операций. Потребление памяти же составит O(n).
Оптимизация и параллелизация
Первую оптимизацию решета предложил сам Эратосфен: раз из всех четных чисел простым является только 2, то давайте сэкономим половину памяти и времени и будем выписывать и высеивать только нечетные числа. Реализация такой модификации алгоритма потребует лишь косметических изменений (код).
Наращивая шаг прогрессии и количество решет (например, при шаге прогрессии 210 нам понадобится 48 решет, что сэкономит еще 4% ресурсов) параллельно росту n, удается увеличить скорость алгоритма в log log 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. Получится примерно следующее:
Для решения этих проблем достаточно выбрать более подходящий тип данных — строку!
Теперь каждый элемент занимает ровно 1 байт, а время работы уменьшилось примерно втрое. Скрипт для измерения скорости.
Решето Аткина
В 1999 году Аткин и Бернштейн предложили новый метод высеивания составных чисел, получивший название решета Аткина. Он основан на следующей теореме.
Из элементарной теории чисел следует, что все простые, большие 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. В комментариях напомнили про решето Сундарама. К сожалению, оно является лишь математической диковинкой и всегда уступает либо решетам Эратосфена и Аткина, либо проверке перебором делителей.
Как найти простые числа?
Красивые аномалии встречаются в каждом предмете, но если есть одна область красоты, с которой согласится большинство математиков, то это простое число.
Эти числа занимают уникальный пьедестал в математике, особенно в области теории чисел. Великие умы потратили бесчисленные часы для расследования этой проблемы, в том числе такие великие умы, как Пол Эрдос, Г.Х. Харди и Сриниваса Рамануджан, и это лишь некоторые из них. Теперь, прежде чем мы углубимся в различные алгоритмы, чтобы найти простые числа, давайте сначала установим предварительное понимание простых чисел.
Что такое простые числа?
Самое техническое определение простых чисел состоит в том, что это натуральное число больше 1 и может быть получено только путем умножения 1 и самого себя. Если бы понимание натуральных чисел было более интуитивным, то можно было бы сказать, что это числа, которые мы используем для подсчета.
Метод Марена Мерсенна
Марен Мерсенн Французский математик
Однако, с появлением компьютеров, они теперь могли выполнять эти вычислительные вычисления, которые раньше делались людьми самым кропотливым и трудоемким образом. Мы определенно достигли более высоких простых чисел Мерсенна и простых чисел на общем уровне. Поиск простых чисел так же активен, как и другие численные поиски, выполняемые компьютерами. Другой числовой поиск, аналогичный движению простых чисел, заключается в добавлении десятичных разрядов к некоторым иррациональным числам, таким как пи (отношение длины окружности к диаметру). Однако непрерывный поиск следующего по величине простого числа существенно сложнее, чем поиск следующей цифры числа Пи.
Даже самые большие компьютеры (суперкомпьютеры) тратят значительное количество времени, чтобы проверить, является ли новое число (которое обычно ошеломляюще огромным) само по себе простым числом, и требуется еще больше времени, чтобы проверить, является ли число основным числом Мерсенна. По этой причине числа Мерсенна представляют большой интерес в области кибербезопасности и криптографии, особенно в отношении шифрования.
В августе 2008 года системный администратор UCLA Эдсон Смит нашел наиболее значимое простое число, известное на тот момент. Смит установил программное обеспечение для Great Internet Mersenne Prime Search (Gimps), проекта распределенных вычислений на добровольной основе. Это число было простым числом Мерсенна длиной 12 978 189 цифр. Чтобы дать представление о том, насколько он велик, на его написание уйдет почти два с половиной месяца, а в случае печати он растянется на 50 км!
Метод простых чисел Ферма
Пьер де Ферма (фр. Pierre de Fermat, 17 августа 1601 — 12 января 1665) — французский математик-самоучка, один из создателей аналитической геометрии, математического анализа, теории вероятностей и теории чисел.
Когда n = 0, m = 2 0 = 1; поэтому F0 = 2 1 + 1 = 2 + 1 = 3, что является простым. Когда n = 1, m = 2 1 = 2; поэтому F1 = 2 2 + 1 = 4 + 1 = 5, что является простым. Когда n = 2, m = 2 2 = 4; следовательно, F2 = 2 4 + 1 = 16 + 1 = 17, что является простым. Когда n = 3, m = 2 3 = 8; следовательно, F3 = 2 8 + 1 = 256 + 1 = 257, что является простым. Когда n = 4, m = 2 4 = 16; следовательно, F4 = 2 16 + 1 = 65536 + 1 = 65537, что является простым числом. Теперь, как вы можете заметить, к тому времени, когда мы достигнем F5, значение достигает 4 294 967 297.
На сегодняшний день мы достигли только F11, даже со всеми лучшими компьютерами и параллельными вычислениями и большой точностью. В конце концов, однако, мы можем сказать, что поиск простых чисел всегда будет идти до бесконечности и дальше!