Даже на языке программирования 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 — это простое число
В С++ можно определить простое число или нет другим способом. Например, таким:
Задачи JS: Как найти простое число + Как найти все простые числа до N | Перебор и Решето Эратосфена
#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 — это простое число
Заключение
Проверка: простое ли число на С++ делается несложно. Чтобы определить просто е число или нет, вы можете воспользоваться одной из описанных выше версий программы проверки на С++, либо придумать собственную.
Проверка простоты числа перебором делителей
Простые числа — это натуральные числа больше единицы, которые делятся нацело только на единицу и на себя. Например, число 3 простое, так как нацело делится только на 1 и 3. Число 4 сложное, так как нацело делится не только на 1 и 4, но также на число 2.
Алгоритм перебора делителей заключается в последовательном делении заданного натурального числа на все целые числа, начиная с двойки и заканчивая значением меньшим или равным квадратному корню из тестируемого числа. Таким образом, в данном алгоритме используется цикл, счетчик итераций которого последовательно принимает значения ряда натуральных чисел от 2 до корня из исследуемого числа.
Перебор делителей применяется в том числе для определения, является ли натуральное число простым, или оно является сложным, то есть составным. Касаемо данной задачи, если хотя бы один делитель делит исследуемое число без остатка, то оно является составным. Если ни одного такого делителя не находится, то число признается простым.
Является ли число простым — Проверяем на языке Си
from math import sqrt n = int(input()) prime = True i = 2 while i sqrt(n): if n % i == 0: prime = False break i += 1 if prime: print(«Простое число») else: print(«Составное число»)
В программе мы сначала предполагаем, что введенное число n является простым, и поэтому присваиваем переменной prime значение True . Далее в цикле перебираются делители (переменная i ) от 2-х до квадратного корня из числа n . Как только встречается первый делитель, на который n делится без остатка, меняем значение prime на False и прерываем работу цикла, так как дальнейшее тестирование числа на простоту смысла не имеет.
Если после выполнения цикла prime осталась истиной, сработает ветка if условного оператора. В случае False , поток выполнения заходит в ветку else .
Если знать о такой особенности циклов в Python как возможность иметь ветку else , то код можно упростить, избавившись от переменной prime и ее проверки условным оператором после завершения работы цикла.
from math import sqrt n = int(input()) i = 2 while i sqrt(n): if n % i == 0: print(«Составное число») break i += 1 else: print(«Простое число»)
Ветка else при циклах (как while , так и for ) срабатывает, если в основном теле цикла не происходило прерывания с помощью break . Если break сработал, то тело else выполняться не будет. При использовании таких конструкций также следует помнить, что если условие в заголовке цикла сразу возвращает ложь (то есть тело цикла не должно выполняться ни разу), код тела else все-равно будет выполнен.
Программы выше будут определять числа 0 и 1 как простые. Это неправильно. Данные числа не являются ни простыми, ни сложными. Для проверки ввода пользователя, можно воспользоваться условным оператором или зациклить запрос числа, пока не будет введено корректное значение:
n = 0 while n 2: n = int(input())
Рассмотрим функцию, которая определяет, является ли число простым:
from math import sqrt def is_prime(n): i = 2 while i sqrt(n): if n % i == 0: return False i += 1 if n > 1: return True a = int(input()) if is_prime(a): print(«Простое число») else: print(«Число НЕ является простым»)
Здесь нет необходимости в прерывании работы цикла с помощью break , так как оператор return выполняет выход из тела всей функции.
Если цикл полностью отработал, выполнится выражение return True , находящееся ниже цикла. Оно помещено в тело условного оператора, чтобы исключить возврат «истины», когда в функцию передаются числа 0 или 1. В этом случае функция вернет объект None .
Программа не защищена от ввода отрицательного числа. При этом будет генерироваться ошибка на этапе извлечения квадратного корня.
Нарисуем блок-схему тестирования числа на простоту (без дополнительных проверок и оператора break ):
from math import sqrt n = int(input()) prime = True i = 2 while i sqrt(n) and prime is True: if n % i == 0: prime = False i += 1 if prime: print(«Простое число») else: print(«Составное число»)
X Скрыть Наверх
Решение задач на Python
Источник: younglinux.info
Как определить простое число
Задача 2.30
Дан одномерный массив А, состоящий из натуральных чисел. Вывести на экран количество простых чисел в массиве.
Для начала напомню, что такое простые числа.
Простое число — это натуральное число, которое имеет ровно два различных натуральных делителя — единицу и самого себя.
То есть если число делится без остатка только на 1 и на самого себя, то такое число является простым.
Например, простыми числами являются 2, 3, 5 и т.п.
А вот 4 уже не является простым, так как делится без остатка не только на 1 и 4, но ещё и на 2.
Если вы подзабыли, что такое натуральное число, то см. здесь.
А теперь перейдём к задаче. По сути нам нужна программа, определяющая простые числа. А уж перебрать элементы массива в цикле и проверить их значения — это дело техники. Заодно мы можем не только подсчитать, но и вывести на экран простые числа массива.
Как определить простое число в Паскале
Алгоритм решения с подробным разбором приведу на Паскале. Решение на С++ можете посмотреть в примере программы на С++.
ВАЖНО!
На этом многие могут ошибиться. В определении сказано, что простое число имеет ровно два различных делителя. Следовательно, число 1 не является простым (также не является простым, так как ноль можно делить на любые числа).
Проверять, является ли число простым, будем с помощью функции, которую сами и создадим. Эта функция будет возвращать TRUE, если число простое.
В функции сначала будем проверять, не является ли число меньше двух. Если да, то это уже не простое число. Если же число равно 2 или 3, то оно является однозначно простым и делать какие-то дополнительные проверки не требуется.
А вот если число N будет больше трёх, то в этом случае в цикле будем перебирать все возможные делители, начиная от 2 до (N-1). Если на какой-то делитель число N делится без остатка, значит, это тоже не простое число. В этом случае мы прерываем цикл (потому что проверять дальше нет смысла), а функция возвращает FALSE.
Проверять, делится ли число на самоё себя нет смысла (поэтому цикл длится только до N-1).
Саму функцию здесь приводить не буду — посмотрите её в примерах программ.
Решение задачи 2.30 на Паскале
program mytask; //**************************************************************** // КОНСТАНТЫ //**************************************************************** const COUNT = 100; //Количество элементов в массиве //**************************************************************** // ФУНКЦИИ И ПРОЦЕДУРЫ //**************************************************************** //**************************************************************** // Проверяет, является ли число простым // ВХОД : N — число // ВЫХОД : TRUE — число N простое, FALSE — не простое //**************************************************************** function IsPrimeNumber(N : WORD) : boolean; var i : WORD; begin Result := TRUE; case N of 0..3 : begin if N < 2 then Result := FALSE; //Не простое число Exit; end; end; for i := 2 to (N-1) do if (N mod i) = 0 then //Не простое число begin Result := FALSE; Break; end; end; var i : WORD; X : WORD = 0; A : array[1..COUNT] of WORD; //**************************************************************** // ОСНОВНАЯ ПРОГРАММА //**************************************************************** begin //Заполнить массив числами for i := 1 to COUNT do A[i] := i; //Подсчитать и выбрать простые числа из массива for i := 1 to COUNT do if IsPrimeNumber(A[i]) then begin Inc(X); Write(A[i], ‘ ‘); end; WriteLn(#10#13’Number of Prime numbers = ‘, X); WriteLn(‘The end. Press ENTER. ‘); ReadLn; end.
Решение задачи 2.30 на С++
#include #include using namespace std; //**************************************************************** // КОНСТАНТЫ //**************************************************************** const int COUNT = 100; //Количество элементов в массиве //**************************************************************** // ФУНКЦИИ И ПРОЦЕДУРЫ //**************************************************************** //**************************************************************** // Проверяет, является ли число простым // ВХОД : N — число // ВЫХОД : TRUE — число N простое, FALSE — не простое //**************************************************************** bool IsPrimeNumber(int N) < bool Res = true; switch (N) < case 0 : Res = false; break; case 1 : Res = false; break; case 2 : Res = true; break; case 3 : Res = true; break; default : for (int i = 2; i < N; i++) if (0 == (N % i)) //Не простое число < Res = false; break; >> return(Res); > //**************************************************************** // ОСНОВНАЯ ПРОГРАММА //**************************************************************** int main(int argc, char *argv[]) < int A[COUNT]; int X = 0; //Заполнить массив числами for (int i = 0; i < COUNT; i++) A[i] = i; //Подсчитать и выбрать простые числа из массива for (int i = 0; i < COUNT; i++) if (IsPrimeNumber(A[i])) < X++; cout ; cout
Источник: info-master.su