Как определить простое число

Условие задачи 2.30

Задача 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 <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++ - это один из самых популярных языков программирования. Не важно, на каком языке программируете лично вы. Но, если вы хотя бы в общих чертах не знаете С++, то это большой пробел в вашем образовании, который надо восполнить как можно быстрее... Подробнее...

Главная
Контакты