Простое число — натуральное (целое положительное) число, имеющее ровно два различных натуральных делителя — единицу и самого себя.
Чтобы проверить является ли какое-то число простым, напрашивается наивный метод решения — проверить делимость его на все натуральные числа от 1 до n (хотя достаточно лишь до квадратного корня из него). Если в какой-то момент остаток от деления даст 0 (то есть число поделилось без остатка), значит оно составное, а в противном случае является простым.
Такой алгоритм прост, но требует довольно много проверок на делимость, из-за чего может быть применён для проверки небольшого числа. А что будет, если применить его для поиска простого числа по заданному номеру n?
Решение кажется очевидным: начнём перебирать подряд числа и проверять их на простоту. Как только обнаружим n простых чисел, остановимся и вернём в результате последнее найденное число. Однако, даже для не очень большого числа n данный метод будет работать чрезвычайно долго, поскольку чем больше будет число, тем дольше будут перебираться его делители.
Простое число (while)
Вот тут нам на помощь и приходит быстрый алгоритм — решето Эратосфена. Данный алгоритм позволяет найти все простые числа в интервале от 2 до N за довольно короткое время, но нам то нужно найти n-ое простое число, а про индексы в данном алгоритме ничего не сказано. Если бы можно было узнать, в каком интервале находится n-ое простое число, то задача была бы мгновенно решена применением решета. Однако как же решить данную задачу, не зная примерное значение числа?
Как работает решето Эратосфена
Проверка простого числа путем создания функции в C++
Вы научитесь проверять, является ли введенное пользователем число простым или нет, передав его в пользовательскую функцию на C++.
#include using namespace std; bool checkPrimeNumber(int); int main() < int n; cout > n; if (checkPrimeNumber(n)) cout bool checkPrimeNumber(int n) < bool isPrime = true; // 0 and 1 are not prime numbers if (n == 0 || n == 1) < isPrime = false; >else < for (int i = 2; i > > return isPrime; >
Enter a positive integer: 23 23 is a prime number.
В этом примере число, введенное пользователем, передается в функцию checkPrimeNumber().
Эта функция возвращает истину, если число, переданное в функцию, является простым числом, и возвращает ложь, если переданное число не является простым числом.
- Преобразование восьмеричного числа в десятичное и наоборот в C++
- Преобразование двоичного числа в восьмеричное и наоборот в C++
- Как перевернуть строку в C++
- Свежие записи
- Функция iscntrl() в C++
- Функция isdigit() в С++
- Функция isblank() в C++
- Функция isgraph() в C++
- Функция islower() в C++
Источник: calmsen.ru
Написать программу которая проверяет является ли целое число простым
Привет Лёва Середнячок
Как узнать простое число или нет?
Написать программу, которая проверяет , является ли целое число , введенное пользователем , простым.
Программа Паскаль
Цикл с пост условием
3 (5 оценок)
Bakalavr 9 лет назад
Светило науки — 72 ответа — 904 помощи
program chet;
var i,k,n:integer;
begin
readln(n);
for i:=1 to n do
begin
if n mod i = 0 then k:=k+1;
end;
if k=2 then writeln(‘число,’,n,’,натуральное’)
else writeln(‘число,’,n,’,не натуральное’);
end.
Источник: vashurok.com