Раздел: Задачи / Простейшие /

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

Основы программирования

Подпишись на новости, чтобы ничего не пропустить


Условие задачи 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;
}

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


Помощь в технических вопросах Помощь в технических вопросах

Помощь студентам. Курсовые, дипломы, чертежи (КОМПАС), задачи по программированию: Pascal/Delphi/Lazarus; С/С++; Ассемблер; языки программирования ПЛК; JavaScript; VBScript; Fortran; Python и др. Разработка (доработка) ПО ПЛК (предпочтение - ОВЕН, CoDeSys 2 и 3), а также программирование панелей оператора, программируемых реле и других приборов систем автоматизации. Подробнее...
Инфо-МАСТЕР ®
Все права защищены ©
e-mail: mail@info-master.su

Яндекс.Метрика