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

Основы программирования
Каждый профессионал когда-то был чайником. Наверняка вам знакомо состояние, когда “не знаешь как начать думать, чтобы до такого додуматься”. Наверняка вы сталкивались с ситуацией, когда вы просто не знаете, с чего начать. Эта книга ориентирована как раз на таких людей, кто хотел бы стать программистом, но совершенно не знает, как начать этот путь. Подробнее...

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

Вступить в группу "Основы программирования"

Подписаться на канал в РУТУБ

Подписаться на Дзен-канал

Подписаться на рассылки по программированию

Как стать программистом 2.0

Эта книга для тех, кто хочет стать программистом. На самом деле хочет, а не просто мечтает. И хочет именно стать программистом с большой буквы, а не просто научиться кулебякать какие-то примитивные программки… Подробнее...

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

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

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