Как проверить является ли число простым в С++
Даже на языке программирования 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 — это простое число
Заключение
Проверка: простое ли число на С++ делается несложно. Чтобы определить просто е число или нет, вы можете воспользоваться одной из описанных выше версий программы проверки на С++, либо придумать собственную.
Мы будем очень благодарны
если под понравившемся материалом Вы нажмёте одну из кнопок социальных сетей и поделитесь с друзьями.
Алгоритм проверки на простоту за 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.
Алгоритмы поиска простых чисел в C#
Простое число — это целое положительное число, имеющее ровно два различных натуральных делителя — единицу и самого себя. Определение того является ли число простым или нет — это одна из самых распространенных задач, решаемых в рамках курса лабораторных работ по информатике. Ниже будет представлена реализация алгоритма поиска простых чисел в C#, а также использование различных циклов для вывода простых чисел.
Задача №1
Проверить является ли число простым и вывести результат вычисления в консоль.
Алгоритм определения простого числа
Для того, чтобы проверить является ли число N простым необходимо:
- Задаем значение N
- Задаем цикл for от 2 до N-1 (счётчик цикла обозначим, например, как i )
- Если остаток от деление N на i равен нулю, то число не является простым — выходим из цикла
- Если остаток от деления N на i не равен нулю, то переходим к следующей итерации цикла
Реализация алгоритма определения простого числа в C#
Метод определения простого числа в C#, реализующий представленный выше алгоритм может быть представлен следующим образом:
Пример определения простых чисел из диапазона от 1 до N
Если по условиям задачи конечное значение диапазона задается в виде числа N , то здесь удобно использовать цикл for или while. Пример программы с использованием цикла for представлен ниже:
Строго говоря, число 1 не является ни простым не составным, поэтому его можно было бы исключить из цикла, что мы и сделаем в следующем примере.
Пример определения заданного количества простых чисел
Задача поиска простых чисел может быть сформулирована и по другому, например, так: найти первые N простых чисел. В этом случае нам будет выгодно использовать цикл while:
Результатом работы программы будет вывод в консоль первых N простых чисел.
Итого
Сегодня мы рассмотрели алгоритм поиска простых чисел и реализовали этот алгоритм в C#. В зависимости от условий задачи, мы использовали различные виды циклов для поиска набора простых чисел.
Является ли число простым
Хочу написать прогу на 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.