Как проверить является ли число простым c
Перейти к содержимому

Как проверить является ли число простым c

  • автор:

Как проверить, является ли число простым

Соавтор(ы): Grace Imson, MA. Грейс Имсон — преподаватель математики с более чем 40 годами опыта. В настоящее время преподает математику в Городском колледже Сан-Франциско, ранее работала на кафедре математики в Сент-Луисском университете. Преподавала математику на уровне начальной, средней и старшей школы, а также колледжа. Имеет магистерскую степень по педагогике со специализацией на руководстве и контроле, полученную в Сент-Луисском университете.

Количество источников, использованных в этой статье: 8. Вы найдете их список внизу страницы.

Количество просмотров этой статьи: 210 608.

В этой статье:

Простые числа — это числа, которые делятся только на себя и на 1. Все остальные числа называются составными числами. Есть множество способов определить, является ли число простым, и все они имеют свои преимущества и недостатки. С одной стороны, некоторые методы отличаются большой точностью, но они довольно сложны, если вы имеете дело с большими числами. С другой стороны, существуют намного более быстрые способы, но они могут привести к неправильным результатам. Выбор подходящего метода зависит от того, с насколько большими числами вы работаете.

Часть 1 из 3:

Тесты простоты

Примечание: во всех формулах n обозначает проверяемое число.

Step 1 Перебор делителей.

Перебор делителей. Достаточно поделить n на все простые числа от 2 до округленного значения(Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): > ).

Step 2 Малая теорема Ферма.

  • Выберем целое число a, такое что 2 ≤ a ≤ n — 1.
  • Если a n (mod n) = a (mod n), то число, вероятно, простое. Если равенство не выполняется, число n является составным.
  • Проверьте данное равенство для нескольких значений a, чтобы увеличить вероятность того, что проверяемое число действительно является простым.

Step 3 Тест Миллера-Рабина.

  • Найдите величины s и d, такие чтобы Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): n-1=2^*d .
  • Выберите целое число a в интервале 2 ≤ a ≤ n — 1.
  • Если a d = +1 (mod n) или -1 (mod n), то n, вероятно, является простым числом. В этом случае перейдите к результату теста. Если равенство не выполняется, перейдите к следующему шагу.
  • Возведите ответ в квадрат (Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): a^> ). Если получится -1 (mod n), то n, вероятно, простое число. В этом случае перейдите к результату теста. Если равенство не выполняется, повторите (Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): a^> и так далее) до Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): a^>d>> .
  • Если на каком-то шаге после возведения в квадрат числа, отличного от Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): \pm 1 (mod n), у вас получилось +1 (mod n), значит n является составным числом. Если Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): a^>d>>\neq \pm 1 (mod n), то n не является простым числом.
  • Результат теста: если n прошло тест, повторите его для других значений a, чтобы повысить степень достоверности.

Часть 2 из 3:

Как работают тесты простоты

Step 1 Перебор делителей.

  • Функция floor(x) округляет число x до ближайшего целого числа, которое меньше или равно x.

Step 2 Узнайте о модульной арифметике.

  • Во многих калькуляторах есть клавиша mod. В конце данного раздела показано, как вручную вычислять эту функцию для больших чисел.

Step 3 Узнайте о подводных камнях малой теоремы Ферма.

Узнайте о подводных камнях малой теоремы Ферма. Все числа, для которых не выполняются условия теста, являются составными, однако остальные числа лишь вероятно относятся к простым. Если вы хотите избежать неверных результатов, поищите n в списке «чисел Кармайкла» (составных чисел, которые удовлетворяют данному тесту) и «псевдопростых чисел Ферма» (эти числа соответствуют условиям теста лишь при некоторых значениях a). [2] X Источник информации

Step 4 Если удобно, используйте тест Миллера-Рабина.

Если удобно, используйте тест Миллера-Рабина. Хотя данный метод довольно громоздок при вычислениях вручную, он часто используется в компьютерных программах. Он обеспечивает приемлемую скорость и дает меньше ошибок, чем метод Ферма. [3] X Источник информации Составное число не будет принято за простое, если провести расчеты для более ¼ значений a. [4] X Источник информации Если вы случайным способом выберете различные значения a и для всех них тест даст положительный результат, можно с достаточно высокой долей уверенности считать, что n является простым числом.

Step 5 Для больших чисел используйте модульную арифметику.

  • Перепишите выражение в более удобном виде: Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): (3^>*3^>) mod 50. При расчетах вручную могут понадобиться дальнейшие упрощения.
  • Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): (3^>*3^>) mod 50 = Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): (3^> mod 50 Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): *3^> mod 50) mod 50. Здесь мы учли свойство модульного умножения.
  • Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): 3^> mod 50 = 43.
  • Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): (3^> mod 50 Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): *3^> mod 50) mod 50 = Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): (43*43) mod 50.
  • Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): =1849 mod 50.
  • Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): =49 .

Для заданного числа N проверить, является ли оно простым. на языке C?

int isPrime(int n) <
if (n for (int i = 2; i * i if (n % i == 0) return 0; // n делится на i без остатка, значит, n составное число
>
return 1; // n не делится на никакое число кроме 1 и самого себя, значит, n простое число
>

int main() <
int n;
scanf(«%d», &n);
printf(«%d», isPrime(n));
return 0;
>

Функция isPrime принимает целочисленный аргумент n и возвращает 1, если n является простым числом, и 0 в противном случае.
Сначала проверяем, является ли n равным 1 или меньшим. Если это так, то n не является простым числом, поэтому возвращаем 0.
Затем мы проверяем, делится ли n на какое-либо число от 2 до корня из n. Если да, то n является составным числом и мы возвращаем 0.
Если никакое число от 2 до корня из n не делит n без остатка, то n является простым числом, поэтому возвращаем 1.
В функции main считываем входное значение n, вызываем функцию isPrime и выводим ее результат.

При этом, return 0 не меняем, так как это требование задачи.

Да не меняй return 0; , он вообще в в этой программе не нужен, соответствующий ему код в программе на C компилятором автоматически сгенерируется и без него 🙂

Является ли число простым

Хочу написать прогу на C++. Она сначала просит ввести число (простое оно или нет, прога проверяет), потом выводит результат на консоль. Объясните, пожалуйста, как сделать или хоть намекните (среда dev-c++ 4.9.9.2), очень прошу.

Отслеживать
81.1k 9 9 золотых знаков 78 78 серебряных знаков 135 135 бронзовых знаков
задан 16 ноя 2011 в 12:40
инклюде димо инклюде димо
45 1 1 золотой знак 1 1 серебряный знак 4 4 бронзовых знака

8 ответов 8

Сортировка: Сброс на вариант по умолчанию

Написать что-то в виде

int n; // ввести n c клавиатуры for (i = 2; i > //вывести что n простое. return 0; 

Алгоритм, конечно, можно заметно ускорить, как минимум в два раза, но для начала хватит.

Отслеживать
31.9k 3 3 золотых знака 19 19 серебряных знаков 56 56 бронзовых знаков
ответ дан 16 ноя 2011 в 13:01
112k 6 6 золотых знаков 93 93 серебряных знака 159 159 бронзовых знаков
должно быть i<=sqrt(n), иначе квадрат простого числа тоже будет простым. 16 ноя 2011 в 14:14

Тогда, наверное, даже лучше набросить сверху единицу, то есть i
16 ноя 2011 в 14:36
Поправь ответ? И ещё нехорошо на каждой итерации квадратный корень считать.
17 окт 2017 в 15:45

А можно проверять делимость по простым числам. А найти их в не очень большом количестве особого труда не составит. =)

Решето Эратосфена (до корня из n). За 1 секунду находит числа до 10^7 примерно.

А дальше перебор делимости (Либо если число уже найдено Эратосфеном, то и перебирать не придётся) на простые числа, если число больше чем 10^7 также до корня из n.

И всё довольно просто и быстро =)

Отслеживать
ответ дан 21 ноя 2011 в 13:03
147 13 13 бронзовых знаков

Довольна старая тема, но всё же добавлю. Есть одна особенность простых чисел — при возведении числа в квадрат, деление этого числа в квадрате на 24 будет давать остаток 1 ( c 2 и 3 не работает, т.к они слишком маленькие , но с остальными числами работает отлично и не тратит много ресурсов для проверки)

int isprime(int num) < if ((num * num) % 24 == 1) < return true; >return false; > 

Отслеживать
3,135 6 6 золотых знаков 18 18 серебряных знаков 34 34 бронзовых знака
ответ дан 16 июл 2019 в 10:23
user344423 user344423

И не только простых, но и составных, что делает данный алгоритм непригодным для определения простых чисел

16 июл 2019 в 11:00
Это не работает с составными числами, только с простыми.youtube.com/watch?v=ZMkIiFs35HQ
– user344423
16 июл 2019 в 21:01

25, 35, 49, 55, 65, 77, 85, 91, 95 и ещё бесконечное количество чисел, которая ваша функция определяет как простые

16 июл 2019 в 21:22

Плюс к тому, кроме 2 и 3, с простого числа 46349 и последующие простые числа определяет как составные

16 июл 2019 в 21:43

В плане эффективности могут намекнуть, например, на тест Рабина-Миллера, но судя по всему, Вам будет проще реализовать проверку тривиальным делением

Отслеживать
ответ дан 16 ноя 2011 в 12:52
3,978 12 12 серебряных знаков 7 7 бронзовых знаков

bool prime(ll n) < for (ll i = 2; i return true; > 

Отслеживать
19.1k 6 6 золотых знаков 30 30 серебряных знаков 44 44 бронзовых знака
ответ дан 16 июн 2015 в 17:19
Елдан Абдрашим Елдан Абдрашим
И правильно минуснули. Зачем в цикле проверять делимость на четные?
16 июн 2015 в 19:03

#include #include using namespace std; int main()< int n, i; bool isPrime = true; cout>n; cout > if(isPrime) cout

Это готовый код

Отслеживать
5,199 4 4 золотых знака 28 28 серебряных знаков 51 51 бронзовый знак
ответ дан 17 окт 2017 в 15:40
Bogdan Pahomov Bogdan Pahomov
46 7 7 бронзовых знаков

В первом ответе допущена неточность. Я бы написал так

bool prostoNumer(int n)

PS: дело в том что пропускает 4. Потому что цикл не работает sqrt(4) == 2, 2 < 2 и поэтому цикл завершает работу с ложным результатом. нужно поправить 2 Отслеживать 845 6 6 серебряных знаков 12 12 бронзовых знаков ответ дан 3 апр 2017 в 10:34 1 1 1 бронзовый знак Это есть в комментариях под принятым ответом 3 апр 2017 в 10:39

Обратите внимание на класс Prime . Простое число — число, имеющее два делителя. Это единица и само это число. Следовательно единица простым числом являться не может, так как она имеет один делитель, значит ее нужно исключить. Для этого воспользуемся условным оператором if . После этого начнем искать делители этого числа (будем перебирать все числа, которые меньше указанного числа), напомню делителем называется число, которое делится на данный делитель без остатка, то есть остаток равен 0. Когда нашли такое число, ставим на него булевое значение false, как пометка о том, что данное число является составным. После выполнения управляющей конструкции for остаются некоторые числа, которые не помечены false, то есть не имеют делителя(отличного от себя и 1), помечаем их как true.

 namespace one < class Program < static void Main(string[] args) < Prime prime = new Prime(); int AmountOfNumbers = 10; for (int i = 2; i < AmountOfNumbers; i++) < if (prime.IsPrime(i)) < Console.WriteLine(i + " простое число."); >else < Console.WriteLine(i + " составное число."); >> > > class Prime < public bool IsPrime(int x) < if (x >1) < for (int i = 2; i < x; i++) < if ((x % i) == 0) < return false; >> return true; > else < return false; >> > > 

Отслеживать
ответ дан 24 фев 2022 в 8:15
EkaterinaR. EkaterinaR.
59 6 6 бронзовых знаков
Код рабочий, но слишком неоптимальный, даже по сравнению с предыдущими ответами
24 фев 2022 в 9:01

Highly active question. Earn 10 reputation (not counting the association bonus) in order to answer this question. The reputation requirement helps protect this question from spam and non-answer activity.

Как проверить является ли число простым в С++

Даже на языке программирования C++ можно проверить является ли число простым несколькими способами.

Вариант первый:

#include

using namespace std;

bool checkPrimeNumber(int);

int main()

int n;

cout

cin >> n;

if (checkPrimeNumber(n))

cout

else

cout

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

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

else

cout

return 0;

>

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

Введите целочисленное положительное значение: 29

29 — это простое число

Заключение

Проверка: простое ли число на С++ делается несложно. Чтобы определить просто е число или нет, вы можете воспользоваться одной из описанных выше версий программы проверки на С++, либо придумать собственную.

Мы будем очень благодарны

если под понравившемся материалом Вы нажмёте одну из кнопок социальных сетей и поделитесь с друзьями.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *