Как проверить является ли число простым в С++
Даже на языке программирования C++ можно проверить является ли число простым несколькими способами.
Вариант первый:
#include <iostream>
using namespace std;
bool checkPrimeNumber(int);
int main() <
int n;
cout << «Введите целочисленное положительное значение: «;
cin >> n;
if (checkPrimeNumber(n))
cout << n << » — это простое число.»;
else
cout << n << » — это значение не является простым числом.»;
return 0;
>
bool checkPrimeNumber(int n) <
bool isPrimeNumber = true;
// 0 и 1 не являются простыми числами
if (n == 0 || n == 1) <
isPrimeNumber = false;
>
else <
for (int i = 2; i <= n / 2; ++i) <
if (n % i == 0) <
isPrimeNumber = false;
break;
>
>
>
return isPrimeNumber;
>
Ели запустить в работу эту программу, тогда в результате будет следующее:
Введите целочисленное положительное значение: 23
23 — это простое число
В С++ можно определить простое число или нет другим способом. Например, таким:
#include <iostream>
using namespace std;
int main() <
int i, n;
bool isPrimeNumber = true;
cout << «Введите целочисленное положительное значение: «;
cin >> n;
// 0 и 1 не являются простыми числами по умолчанию
if (n == 0 || n == 1) <
isPrimeNumber = false;
>
else <
for (i = 2; i <= n / 2; ++i) <
if (n % i == 0) <
isPrimeNumber = false;
break;
>
>
>
if (isPrimeNumber)
cout << n << » — это простое число»;
else
cout << n << » — это значение не является простым числом»;
return 0;
>
Если запустить эту программу в работу, тогда ее результатом будет, как и в предыдущем случае, например, такое:
Введите целочисленное положительное значение: 29
29 — это простое число
Заключение
Проверка: простое ли число на С++ делается несложно. Чтобы определить просто е число или нет, вы можете воспользоваться одной из описанных выше версий программы проверки на С++, либо придумать собственную.
Мы будем очень благодарны
если под понравившемся материалом Вы нажмёте одну из кнопок социальных сетей и поделитесь с друзьями.
Программирование на C, C# и Java
Уроки программирования, алгоритмы, статьи, исходники, примеры программ и полезные советы
ОСТОРОЖНО МОШЕННИКИ! В последнее время в социальных сетях участились случаи предложения помощи в написании программ от лиц, прикрывающихся сайтом vscode.ru. Мы никогда не пишем первыми и не размещаем никакие материалы в посторонних группах ВК. Для связи с нами используйте исключительно эти контакты: vscoderu@yandex.ru, https://vk.com/vscode
Является ли число простым — Проверяем на языке Си
Напишем на языке Си программу, проверяющую является ли число простым. Для проверки будем использовать простейший алгоритм, основанный непосредственно на определении простого числа.
Простое число — определение
Простое число — это натуральное число (то есть целое и положительное), большее, чем единица, которое делится без остатка только на единицу и само на себя.
Список простых чисел (приведем до ста) начинается так: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97…
Функция на Си, проверяющая — является ли число простым
Напишем на языке Си функцию, которая будет проверять — простое ли число. И возвращать результат проверки в виде логической величины bool: true (да) или false (нет).
Алгоритм проверки числа n на простоту строится на определении термина простого числа.
Во-первых число n должно быть больше 1 (проверяем это в строке 5 с помощью условного оператора if), а во-вторых проверяемое число должно иметь только два делителя: 1 и n (проверяем это в строках 8-10 с помощью цикла for и оператора if).
Для работы данного метода требуется подключить заголовочный файл stdbool.h в начале файла с исходным кодом. В stdbool.h содержится определение логических констант true и false, поскольку в чистой версии языка Си они отсутствуют.
Является ли число простым
Хочу написать прогу на C++. Она сначала просит ввести число (простое оно или нет, прога проверяет), потом выводит результат на консоль. Объясните, пожалуйста, как сделать или хоть намекните (среда dev-c++ 4.9.9.2), очень прошу.
Написать что-то в виде
Алгоритм, конечно, можно заметно ускорить, как минимум в два раза, но для начала хватит.
А можно проверять делимость по простым числам. А найти их в не очень большом количестве особого труда не составит. =)
Решето Эратосфена (до корня из n). За 1 секунду находит числа до 10^7 примерно.
А дальше перебор делимости (Либо если число уже найдено Эратосфеном, то и перебирать не придётся) на простые числа, если число больше чем 10^7 также до корня из n.
И всё довольно просто и быстро =)
Довольна старая тема, но всё же добавлю. Есть одна особенность простых чисел — при возведении числа в квадрат, деление этого числа в квадрате на 24 будет давать остаток 1 ( c 2 и 3 не работает, т.к они слишком маленькие , но с остальными числами работает отлично и не тратит много ресурсов для проверки)
В плане эффективности могут намекнуть, например, на тест Рабина-Миллера, но судя по всему, Вам будет проще реализовать проверку тривиальным делением
Это готовый код
В первом ответе допущена неточность. Я бы написал так
PS: дело в том что пропускает 4. Потому что цикл не работает sqrt(4) == 2, 2 < 2 и поэтому цикл завершает работу с ложным результатом. нужно поправить 2 <= 2
Обратите внимание на класс Prime . Простое число — число, имеющее два делителя. Это единица и само это число. Следовательно единица простым числом являться не может, так как она имеет один делитель, значит ее нужно исключить. Для этого воспользуемся условным оператором if . После этого начнем искать делители этого числа (будем перебирать все числа, которые меньше указанного числа), напомню делителем называется число, которое делится на данный делитель без остатка, то есть остаток равен 0. Когда нашли такое число, ставим на него булевое значение false, как пометка о том, что данное число является составным. После выполнения управляющей конструкции for остаются некоторые числа, которые не помечены false, то есть не имеют делителя(отличного от себя и 1), помечаем их как true.
Алгоритмы поиска простых чисел
«Самое большое простое число 2 32582657 -1. И я с гордостью утверждаю, что запомнил все его цифры… в двоичной форме».
Карл Померанс
Натуральное число называется простым, если оно имеет только два различных делителя: единицу и само себя. Задача поиска простых чисел не дает покоя математикам уже очень давно. Долгое время прямого практического применения эта проблема не имела, но все изменилось с появлением криптографии с открытым ключом. В этой заметке рассматривается несколько способов поиска простых чисел, как представляющих исключительно академический интерес, так и применяемых сегодня в криптографии.
Решето Эратосфена
Решето Эратосфена — алгоритм, предложенный древнегреческим математиком Эратосфеном. Этот метод позволяет найти все простые числа меньше заданного числа n. Суть метода заключается в следующем. Возьмем набор чисел от 2 до n. Вычеркнем из набора (отсеим) все числа делящиеся на 2, кроме 2. Перейдем к следующему «не отсеянному» числу — 3, снова вычеркиваем все что делится на 3. Переходим к следующему оставшемуся числу — 5 и так далее до тех пор пока мы не дойдем до n. После выполнения вышеописанных действий, в изначальном списке останутся только простые числа.
Алгоритм можно несколько оптимизировать. Так как один из делителей составного числа n обязательно , алгоритм можно останавливать, после вычеркивания чисел делящихся на .
Иллюстрация работы алгоритма из Википедии:
Сложность алгоритма составляет , при этом, для хранения информации о том, какие числа были вычеркнуты требуется памяти.
Существует ряд оптимизаций, позволяющих снизить эти показатели. Прием под названием wheel factorization состоит в том, чтобы включать в изначальный список только числа взаимно простые с несколькими первыми простыми числами (например меньше 30). В теории предлагается брать первые простые примерно до . Это позволяет снизить сложность алгоритма в раз. Помимо этого для уменьшения потребляемой памяти используется так называемое сегментирование. Изначальный набор чисел делится на сегменты размером и для каждого сегмента решето Эратосфена применяется по отдельности. Потребление памяти снижается до .
Решето Аткина
Более совершенный алгоритм отсеивания составных чисел был предложен Аткином и Берштайном и получил название Решето Аткина. Этот способ основан на следующих трех свойствах простых чисел.
Если n — положительное число, не кратное квадрату простого числа и такое, что . То n — простое, тогда и только тогда, когда число корней уравнения нечетно.
Если n — положительное число, не кратное квадрату простого числа и такое, что . То n — простое, тогда и только тогда, когда число корней уравнения нечетно.
Если n — положительное число, не кратное квадрату простого числа и такое, что . То n — простое, тогда и только тогда, когда число корней уравнения нечетно.
Доказательства этих свойств приводятся в этой статье.
На начальном этапе алгоритма решето Аткина представляет собой массив A размером n, заполненный нулями. Для определения простых чисел перебираются все . Для каждой такой пары вычисляется , , и значение элементов массива , , увеличивается на единицу. В конце работы алгоритма индексы всех элементов массива, которые имеют нечетные значения либо простые числа, либо квадраты простого числа. На последнем шаге алгоритма производится вычеркивание квадратов оставшихся в наборе чисел.
Из описания алгоритма следует, что вычислительная сложность решета Аткина и потребление памяти составляют . При использовании wheel factorization и сегментирования оценка сложности алгоритма снижается до , а потребление памяти до .
Числа Мерсенна и тест Люка-Лемера
Конечно при таких показателях сложности, даже оптимизированное решето Аткина невозможно использовать для поиска по-настоящему больших простых чисел. К счастью, существуют быстрые тесты, позволяющие проверить является ли заданное число простым. В отличие от алгоритмов решета, такие тесты не предназначены для поиска всех простых чисел, они лишь способны сказать с некоторой вероятностью, является ли определенное число простым.
Один из таких методов проверки — тест Люка-Лемера. Это детерминированный и безусловный тест простоты. Это означает, что прохождение теста гарантирует простоту числа. К сожалению, тест предназначен только для чисел особого вида , где p — натуральное число. Такие числа называются числами Мерсенна.
Тест Люка-Лемера утверждает, что число Мерсенна простое тогда и только тогда, когда p — простое и делит нацело -й член последовательности задаваемой рекуррентно: для .
Для числа длиной p бит вычислительная сложность алгоритма составляет .
Благодаря простоте и детерминированности теста, самые большие известные простые числа — числа Мерсенна. Самое большое известное простое число на сегодня — , его десятичная запись состоит из 24,862,048 цифр. Полюбоваться на эту красоту можно здесь.
Теорема Ферма и тест Миллера-Рабина
Простых чисел Мерсенна известно не очень много, поэтому для криптографии с открытым ключом необходим другой способ поиска простых чисел. Одним из таким способов является тест простоты Ферма. Он основан на малой теореме Ферма, которая гласит, что если n — простое число, то для любого a, которое не делится на n, выполняется равенство . Доказательство теоремы можно найти на Википедии.
Тест простоты Ферма — вероятностный тест, который заключается в переборе нескольких значений a, если хотя бы для одного из них выполняется неравенство , то число n — составное. В противном случае, n — вероятно простое. Чем больше значений a использовано в тесте, тем выше вероятность того, что n — простое.
К сожалению, существуют такие составные числа n, для которых сравнение выполняется для всех a взаимно простых с n. Такие числа называются числам Кармайкла. Составные числа, которые успешно проходят тест Ферма, называются псевдопростыми Ферма. Количество псевдопростых Ферма бесконечно, поэтому тест Ферма — не самый надежный способ определения простых чисел.
Тест Миллера-Рабина
Более надежных результатов можно добиться комбинируя малую теорему Ферма и тот факт, что для простого числа p не существует других корней уравнения , кроме 1 и -1. Тест Миллера-Рабина перебирает несколько значений a и проверяет выполнение следующих условий.
Пусть p — простое число и , тогда для любого a справедливо хотя бы одно из условий:
- Существует целое число r < s такое, что
Чем больше свидетелей простоты найдено, тем выше вероятность того, что n — простое. Согласно теореме Рабина вероятность того, что случайно выбранное число a окажется свидетелем простоты составного числа составляет приблизительно .
Следовательно, если проверить k случайных чисел a, то вероятность принять составное число за простое .
Сложность работы алгоритма , где k — количество проверок.
Благодаря быстроте и высокой точности тест Миллера-Рабина широко используется при поиске простых чисел. Многие современные криптографические библиотеки при проверке больших чисел на простоту используют только этот тест и, как показал Мартин Альбрехт в своей работе , этого не всегда оказывается достаточно.
Он смог сгенерировать такие составные числа, которые успершно прошли тест на простоту в библиотеках OpenSSL, CryptLib, JavaScript Big Number и многих других.
Тест Люка и Тест Baillie–PSW
Чтобы избежать уязвимости, связанные с ситуациями, когда сгенерированное злоумышленником составное число, выдается за простое, Мартин Альбрехт предлагает использовать тест Baillie–PSW. Несмотря на то, что тест Baillie–PSW является вероятностным, на сегодняшний день не найдено ни одно составное число, которое успешно проходит этот тест. За нахождение подобного числа в 1980 году авторы алгоритма пообещали вознаграждение в размере $30. Приз пока так и не был востребован.
Ряд исследователей проверили все числа до и не обнаружили ни одного составного числа, прошедшего тест Baillie–PSW. Поэтому, для чисел меньше тест считается детерминированным.
Суть теста сводится к последовательной проверке числа на простоу двумя различными методами. Один из этих методов уже описанный выше тест Миллера-Рабина. Второй — тест Люка на сильную псевдопростоту.
Тест Люка на сильную псевдопростоту
Последовательности Люка — пары рекуррентных последовательностей , описываемые выражениями:
Пусть и — последовательности Люка, где целые числа P и Q удовлетворяют условию
Найдем такие r, s для которых выполняется равенство
Для простого числа n выполняется одно из следующих условий:
- n делит
- n делит для некоторого j < r
Вероятность того, что составное число n успешно пройдет тест Люка для заданной пары параметров P, Q не превышает 4/15. Следовательно, после применения теста k раз, эта вероятность составляет .
Тесты Миллера-Рабина и Люка производят не пересекающиеся множества псевдопростых чисел, соответственно если число p прошло оба теста, оно простое. Именно на этом свойстве основывается тест Baillie–PSW.
Заключение
В зависимости от поставленной задачи, могут использоваться различные методы поиска простых чисел. К примеру, при поиске больших простых чисел Мерсенна, сперва, при помощи решета Эратосфена или Аткина определяется список простых чисел до некоторой границы, предположим, до . Затем для каждого числа p из списка, с помощью теста Люка-Лемера, на простоту проверяется .
Чтобы сгенерировать большое простое число в криптографических целях, выбирается случайное число a и проверяется тестом Миллера-Рабина или более надежным Baillie–PSW. Согласно теореме о распределении простых чисел, у случайно выбранного числа от 1 до n шанс оказаться простым примерно равен . Следовательно, чтобы найти простое число размером 1024 бита, достаточно перебрать около тысячи вариантов.