[АП 2022/06] - свежий номер журнала
Как определить код ошибки при операциях ввода-вывода
Ваша первая программа на Си Шарп в Visual Studio - конечно же Hello World
[АП 2022/05] - свежий номер журнала
Как удалить пустую папку в Паскале

Как стать успешным фрилансером
Раздел: Задачи / Простейшие /
Как определить простое число
![]() |
|
Условие задачи 2.30
Задача 2.30
Дан одномерный массив А, состоящий из натуральных чисел. Вывести на экран количество простых чисел в массиве.
Для начала напомню, что такое простые числа.
Простое число - это натуральное число, которое имеет ровно два различных натуральных делителя - единицу и самого себя.
То есть если число делится без остатка только на 1 и на самого себя, то такое число является простым.
Например, простыми числами являются 2, 3, 5 и т.п.
А вот 4 уже не является простым, так как делится без остатка не только на 1 и 4, но ещё и на 2.
Если вы подзабыли, что такое натуральное число, то см. здесь.
А теперь перейдём к задаче. По сути нам нужна программа, определяющая простые числа. А уж перебрать элементы массива в цикле и проверить их значения - это дело техники. Заодно мы можем не только подсчитать, но и вывести на экран простые числа массива.
Как определить простое число в Паскале
Алгоритм решения с подробным разбором приведу на Паскале. Решение на С++ можете посмотреть в примере программы на С++.
ВАЖНО!
На этом многие могут ошибиться. В определении сказано, что простое число имеет
ровно два различных делителя. Следовательно, число 1 не является простым (также не является простым, так как ноль можно делить на любые числа).
Проверять, является ли число простым, будем с помощью функции, которую сами и создадим. Эта функция будет возвращать TRUE, если число простое.
В функции сначала будем проверять, не является ли число меньше двух. Если да, то это уже не простое число. Если же число равно 2 или 3, то оно является однозначно простым и делать какие-то дополнительные проверки не требуется.
А вот если число N будет больше трёх, то в этом случае в цикле будем перебирать все возможные делители, начиная от 2 до (N-1). Если на какой-то делитель число N делится без остатка, значит, это тоже не простое число. В этом случае мы прерываем цикл (потому что проверять дальше нет смысла), а функция возвращает FALSE.
Проверять, делится ли число на самоё себя нет смысла (поэтому цикл длится только до N-1).
Саму функцию здесь приводить не буду - посмотрите её в примерах программ.
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.
#include <cstdlib> #include <iostream> 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 << A[i] << " "; }; cout << endl << "Number of Prime numbers = " << X << endl; system("PAUSE"); return EXIT_SUCCESS; }

Подписаться на канал в YouTube
Вступить в группу "Основы программирования" Подписаться на рассылки по программированию |
![]() |
Основы C++
C++ - это один из самых популярных языков программирования. Не важно, на каком языке программируете лично вы. Но, если вы хотя бы в общих чертах не знаете С++, то это большой пробел в вашем образовании, который надо восполнить как можно быстрее... Подробнее... |