Как найти простое число pascal

Простые числа – это натуральные числа, большие единицы, которые имеют только два делителя: единицу и само это число.

Примеры простых чисел: 2 , 3, 5, 7, 11, 13…

(Единица не является простым числом!)

Существует множество задач, связанных с простыми числами, и хотя формулируются они достаточно просто, решить их бывает очень трудно. Некоторые свойства простых чисел еще не открыты. Это побудило немецкого математика Германа Вейля (Wayl, 1885-1955) так охарактеризовать простые числа: «Простые числа – это такие существа, которые всегда склонны прятаться от исследователя».

Во все времена люди хотели найти как можно большее простое число. Пока люди считали только при помощи карандаша и бумаги, им нечасто удавалось обнаружить новые простые числа. До 1952 г. самое большое известное простое число состояло из 39 цифр. Теперь поиском все больших простых чисел занимаются компьютеры. Это может представлять интерес для любителей рекордов.

Не будем гнаться за рекордами, а рассмотрим несколько алгоритмов нахождения простых чисел.

Задача 1. Определение простого числа.

Составить программу, которая будет проверять, является ли введенное число простым.

Самый простой путь решения этой задачи – проверить, имеет ли данное число n (n >= 2) делители в интервале [2; n-1]. Если делители есть, число n – составное, если – нет, то – простое. При реализации алгоритма разумно делать проверку на четность введенного числа, поскольку все четные числа делятся на 2 и являются составными числами, то, очевидно, что нет необходимости искать делители для этих чисел. Логическая переменная flag в программе выступает в роли “флаговой” переменной и повышает наглядность программы, так, если flag = true, то n –простое число; если у числа n есть делители, то “флаг выключаем” с помощью оператора присваивания flag:= false, таким образом, если flag = false, то n – составное число.

  var  
  n,i: longint;
  flag: boolean;
  begin  writeln('vvod n');
  read(n);  
  if n = 2 then flag := true
         else if not odd (n) then flag :=  false           
         else  begin                 
              flag := true;                 
              for i := 2 to n-1 do                 
              if n mod i = 0 then flag  := false                 
              end;
  if flag then writeln('Yes') else writeln('No'); 
  readln;
  end.

Задача 2. Нахождение простых чисел в заданном интервале.

Составить программу, которая напечатает все простые числа в заданном интервале [2, m], для m>3 и подсчитает их количество.

Для реализации данного алгоритма необходимо проверить каждое число, находящееся в данном интервале, – простое оно или нет. Однако для этого машине пришлось бы потратить много времени. Поэтому подумаем, каким образом можно оптимизировать алгоритм, описанный в задаче 1, применительно к задаче 2?

Будем использовать следующие приемы оптимизации алгоритма:

1. рассматривать только нечетные числа;
2. использовать свойство: наименьшее число, на которое делится натуральное число n, не превышает целой части квадратного корня из числа n;
3. прерывать работу цикла, реализующего поиск делителей числа, при нахождении первого же делителя с помощью процедуры Break, которая реализует немедленный выход из цикла и передает управление оператору, стоящему сразу за оператором цикла.

Как правило, учащиеся сами догадываются о приемах №1 и №3, но не всегда знают, как реализовать в программе досрочное завершение цикла, прием же №2 для них не очевиден, поэтому, возможно, учителю следует остановиться на нем более подробно или же привести полное доказательство этого утверждения.

Счетчик чисел будет находиться в переменной k. Когда очередное простое число найдено, он увеличивается на 1. Простые числа выводятся по 10 в строке, как только значение счетчика становится кратным 10, курсор переводится на новую строку.

 var
 m,n,i,k: longint;
 flag: boolean;
 begin
 writeln('vvod m>3');
 readln(m);
 write('      2      3');
 n:=3; k := 2;  n := n+2;
 while n <= m do begin
 flag := true;
 for i := 2 to round(sqrt(n)) do
   if n mod i = 0 then begin flag :=  false;
                    break
                end;
   if flag then begin
                write(n:7);
                k := k+1;
                if k mod 10 = 0 then writeln
                end;
 n := n+2
 end;
 writeln;
 writeln('kol-vo = ',k);
 readln
 end.

Близнецы

Два нечетных простых числа, разнящихся на два, называются близнецами. Близнецами являются, например, числа 5 и 7, 11 и 13, 17 и 19 и т.д. В начале натурального ряда такие пары чисел встречаются достаточно часто, но, по мере того как мы продвигаемся в область больших чисел, их становится все меньше и меньше. Известно, что в первой сотне имеется целых 8 близнецов, дальше они расположены очень неравномерно, их можно обнаружить все реже и реже, гораздо реже, нежели сами простые числа. До сих пор неясно, конечно ли число близнецов. Более того, еще не найден способ, посредством которого можно было бы разрешить эту проблему.

Задача 3. Поиск пар чисел близнецов.

Написать программу, которая будет находить все числа близнецы в интервале [2; 1000] и подсчитывать количество пар чисел близнецов.

Фактически будем использовать алгоритм и программу Задачи 2. В этом алгоритме нужно использовать дополнительные переменные для хранения двух “последних” простых чисел и проверять условие наличия близнецов – их разность должна быть равна двум.

 var
 m,n,n1,n2,i,k: longint;
 flag: boolean;
 begin
 m :=1000;
 n1 := 2; n2 := 3; n := n2+2; k:=0;
 while n <= m do begin
 flag := true;
 for i := 2 to round(sqrt(n)) do
   if n mod i = 0 then begin flag := false;
                    break
                end;
   if flag then begin  n1 := n2; n2 := n;
                 if (n2 -n1) = 2 then  begin
                               k := k+1;
                               write(n1:4,n2:4,' ');
                               if k mod 5 = 0 then writeln
                               end
             end;
 n := n+2
 end;
 writeln;
 writeln('kol -vo par =',k);
 readln
 end.

Задача 4. Нахождение простых чисел в заданном интервале с выводом в выходной файл.

Реализовать алгоритм задачи 2 с выводом простых чисел в выходной файл по 10 в строке. Последняя строка файла должна содержать информацию о количестве простых чисел в заданном интервале.

 var
 m,n,i,k: longint;
 flag: boolean;
 f:text;
 begin
 assign(f,'output.txt'); rewrite(f);
 writeln('vvod m > 3');
 readln(m);
 write(f,'  2  3');
 n:=3; k := 2;  n := n+2;
 while n <= m do begin
 flag := true;
 for i := 2 to round(sqrt(n)) do
   if n mod i = 0 then begin flag := false;
                    break
                end;
   if flag then begin
            write(f,n:7);
            k := k+1;
            if k mod 10 = 0 then  writeln(f)
            end;
 n := n+2
 end;
 writeln(f);
 writeln(f,'kol-vo = ',k);
 close(f)
 end.

Задача 5. Приемы оптимизации алгоритма задачи 4.

Оптимизировать алгоритм задачи 4 следующим образом: найденные простые числа записывать в файл, делимость очередного кандидата проверять только на числа из этого файла.

Словесное описание алгоритма:

1. Вводим правую границу диапазона – m;
2. Записываем двойку и тройку в файл;
3. Пока очередное нечетное число i <= m :
   1. проверять очередное нечетное число на наличие делителей из данного файла;
   2. если есть делители, рассматривать очередное нечетное число, если нет – производить дозапись в “хвост” файла.
4. По окончании просмотра диапазона ( i > m ), вывести в файл количество простых чисел.

{Простые  до m}
   label n1;
   var 
   m,i,j,k,q : longint;
   f : text;
   begin
      assign(f,'output.txt');
      rewrite(f);
      Writeln('vvod  m');  {m – правая граница диапазона чисел}
      readln(m);
      k := 0;             {k – счетчик количества  простых чисел}
      if  m >= 2 then begin
                   write(f,'  ':6,'2',' ':6);
                   k:=k+1
                 end;
      if m >= 3 then begin
                  write(f,'3');
                  k:=k+1
                end;
      close(f);
      i:=5;                {В i находится текущее  нечетное число}
      while  i <= m do
       begin  
        reset(f);
         {проверка делимости i на простые числа  q из файла}
         for j:=1  to k do
           begin
            read(f,q);
            if (q*q>i) then break;
            if (i mod q=0) then goto n1
           end;
        close(f); 
             {дозапись в ‘хвост’ файла простых  чисел}
        append(f);
            k:=k+1;
            Write (f,i:7);
            if k mod 10 = 0 then  writeln(f);
            close(f);
        {следующее нечетное число I  <= m}
        n1: i:=i+2
        end;
       {дозапись в конец файла количества простых  чисел} 
        append(f);
   writeln(f);
   writeln(f,'     kol -vo = ',k);
   close(f)
   end.

Эратосфеново решето 

Греческий математик Эратосфен (275-194 гг. до н.э.) предложил интересный метод нахождения простых чисел в интервале [2; n]. Он написал на папирусе, натянутом на рамку, все числа от 2 до 10000 и прокалывал составные числа. Папирус стал, как решето, которое “просеивает” составные числа, а простые оставляет. Поэтому такой метод называется Эратосфеновым решетом. Рассмотрим подробнее этот метод. 

Пусть написаны числа от 2 до n:

2 3 4 5 6 7 8 9 10 11 12 . . .

Первое неперечеркнутое число в строке является простым. Таким образом, 2 – простое число. Начинаем “просеивание” с него, перечеркивая все числа, которые делятся на 2:

2 3 4 5 6 7 8 9 10 11 12 . . .

Далее берем следующее по порядку неперечеркнутое число и перечеркиваем все числа, кратные ему и т. д. Таким образом, мы перечеркнем все составные числа, а простые останутся неперечеркнутыми:

2 3 4 5 6 7 8 9 10 11 12 . . .

Все числа указанного интервала можно рассматривать как множество и в дальнейшем из этого множества будем исключать (отсеивать) все составные числа.

Задача 6. Нахождение простых чисел с помощью решета Эратосфена.

Реализовать алгоритм решета Эратосфена с помощью организации работы с множествами.

Словесное описание алгоритма:

1. Выделим из первых n натуральных чисел все простые числа (решето Эратосфена).
2. Вначале формируем множество BeginSet, состоящее из всех целых чисел в диапазоне от 2 до n. Множество PrimerSet будет содержать искомые простые числа.
3. Затем циклически повторим действия:
   1. взять из BeginSet первое входящее в него число next и поместить его в PrimerSet;
   2. удалить из BeginSet число next и все другие числа, кратные ему, т. е. 2* next, 3* next и т. д.

Цикл повторяется до тех пор, пока множество BeginSet не станет пустым. Программу нельзя использовать для произвольного n, т. к. в любом множестве не может быть больше 256 элементов. (Для расширения интервала простых чисел можно разбить одно большое множество на несколько маленьких, т. е. представить большое множество в виде массива малых множеств. Этот случай рассматривать не будем. Можно предложить наиболее заинтересованным учащимся самостоятельно рассмотреть этот вариант.)

{Выделение всех простых чисел из первых n целых}
 const
 n = 255; {Количество элементов исходного множества}
 type
 SetOfNumber = set of 1..n;
 var
 n1, next, i: word;                    {Вспомогательные  переменные}
 BeginSet,                             {Исходное  множество}
 PrimerSet: SetOfNumber;               {Множество простых чисел}
 begin
   BeginSet := [2..n];                 {Создаем исходное множество}
   PrimerSet  :=[2];                 {Поместить в PrimerSet  первое число из BeginSet}
   next := 2;                          {Первое простое  число}
    while BeginSet  <> [] do            {Начало  основного цикла}
          begin
           n1 := next;   {n1 –число, кратное  очередному простому (next)}
            {Цикл удаления из исходного  множества непростых чисел:} 
           while n1  <= n do
  begin
  Exclude(BeginSet,n1);
  n1 := n1+next         {Следующее кратное}
  end;        {Конец цикла  удаления}
  Include(PrimerSet,next);
  {Получение следующего простого, которое  есть первое невычеркнутое
  из исходного множества}

  repeat
  Inc(next);
  until  (next in BeginSet) or (next > n)
  end;  {Конец основного цикла}
  {Вывод результатов:}

  for  i := 1 to n do
  if i in PrimerSet then write(i:5);
  readln
  end.

Литература:

1. Е.В. Андреева Методика обучения основам программирования на уроках информатики. Лекции 1-8. – М.: Педагогический университет «Первое сентября», 2006.
2. В.А. Дагене, Г.К. Григас, А.Ф. Аугутис 100 задач по программированию. – М.: Просвещение, 1993. – 255 с.
3. В.В. Фаронов Турбо Паскаль 7.0. Начальный курс. Учебное пособие. – М.: «Нолидж», 1999. – 616 с.

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

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

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

В этой публикации решим следующую задачу:

Вывести все простые числа из некоторого диапазона с использованием алгоритма “Решето Эратосфена”.

Простое число – это натуральное число, имеющее ровно 2 делителя: 1 и само число. Например, 2, 3, 5, 7, 11.

Для быстрого поиска простых чисел будем использовать алгоритм “Решето Эратосфена”, заключающийся в просеивании последовательности чисел так, что составные числа последовательности вычеркиваются.

Идея алгоритма

В упорядоченной последовательности натуральных чисел возьмем число k, равное 2 – первому простому числу, и вычеркнем из последовательности все числа, кратные k: 2k, 3k, 4k, …, ik (ik≤N). Далее, в качестве k возьмем следующее за 2 число – это 3, и вычеркнем все кратные 3 числа (6, 9, 12, …).

Слово “вычеркнем” следует понимать так: сделаем число нулем.

Как будем решать задачу

Последовательность натуральных чисел сохраним в массиве. Номера ячеек отождествим с числами. Ячейки с номерами 0 и 1 должны быть равны 0 (0 и 1 не являются простыми числами).

Внешний цикл запустим по k от 2 до N.

Если ячейка a[k] хранит число, не равное 0, то возьмем j=k и во внутреннем цикле пока j<=N-k, с шагом j=j+k, будем обнулять ячейку a[j].

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

var a:array of integer;

    k,j,n:integer;

begin

  {простые числа до 500}

  n:=500;

  setlength(a,n+1);

  for k:=0 to n do a[k]:=k;

  a[1]:=0;

  for k:=2 to n do

  begin

    if a[k]<>0 then  

      begin 

       j:=k;

       while (j<=n-k) do

        begin

         j:=j+k;

         a[j]:=0;

        end;

      end;

  end;

  a.Where(k->k<>0).print; {вывод элементов массива, не равных 0}

end.

Время выполнения программы

Сравним время выполнения программ для поиска простых чисел в диапазоне от 0 до 50 000 с использованием алгоритма “Решето Эратосфена” и алгоритма, в котором для каждого числа считается количество его делителей.

Очевидно, что программа “Решето Эратосфена” ищет простые числа быстрее.

Для промежутка чисел [0; 100 000] время выполнения программы составило 0.096 с; программа, подсчитывающая количество делителей, выполнилась за 46.2 с.

Уменьшить время выполнения программы, подсчитывающей количество делителей, можно за счет поиска сразу двух делителей, идя в цикле до корня квадратного от числа k. 

Таблица простых чисел до 200