Глиф Учебники

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

Справочник · Pascal · 1 минута чтения

Перебирайте делители от 2, пока d * d <= n. Если ни один не подошёл — число простое:

Pascal
program PrimeCheck;
var
  n, d: longint;
begin
  readln(n);
  if n < 2 then
    writeln(n, ' не является простым')
  else
  begin
    d := 2;
    while (d * d <= n) and (n mod d <> 0) do
      d := d + 1;
    if d * d > n then
      writeln(n, ' — простое')
    else
      writeln(n, ' делится на ', d, ', не простое');
  end;
end.
Ввод
91
Вывод
91 делится на 7, не простое

Цикл останавливается либо на первом делителе, либо когда d * d перерос n. После цикла достаточно проверить, по какой причине он закончился.

Почему до корня

Делители идут парами: 91 = 7 · 13, 36 = 4 · 9 = 6 · 6. В каждой паре один делитель не больше корня из числа. Значит, если до корня делителей нет, их нет и дальше. Для числа около миллиона это тысяча проверок вместо миллиона.

Условие пишут как d * d <= n, а не d <= sqrt(n): так обходятся без дробных чисел и их погрешностей.

Особые случаи

Функция IsPrime

Проверку удобно оформить функцией и вызывать для многих чисел:

Pascal
function IsPrime(x: longint): boolean;
var
  d: longint;
begin
  IsPrime := x >= 2;
  d := 2;
  while d * d <= x do
  begin
    if x mod d = 0 then
    begin
      IsPrime := false;
      exit;
    end;
    d := d + 1;
  end;
end;

Функцию описывают перед главным begin программы, а вызывают в условии: if IsPrime(n) then …. Пример вывода всех простых до n с этой функцией — в уроке Задачи школьного курса.

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

Чтобы найти все простые числа до N, быстрее не проверять каждое, а вычёркивать кратные: 2 простое — вычёркиваются 4, 6, 8…; 3 простое — вычёркиваются 9, 12, 15…; и так далее. Что осталось невычеркнутым — простые.

Pascal
program Sieve;
const
  N = 50;
var
  composite: array[2..N] of boolean;
  i, j: integer;
begin
  for i := 2 to N do
    composite[i] := false;
  for i := 2 to N do
    if not composite[i] then
    begin
      write(i, ' ');
      j := i * i;
      while j <= N do
      begin
        composite[j] := true;
        j := j + i;
      end;
    end;
  writeln;
end.
Вывод
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47

Вычёркивать начинают с i * i: меньшие кратные уже вычеркнуты меньшими простыми. Массив composite («составное») сначала заполняется false — пока ничего не вычеркнуто.

Подводные камни