Задачи / Числа / Проверка числа на простоту

Проверка числа на простоту: блок-схема и алгоритм

Число простое, если у него ровно два делителя: 1 и само число. Достаточно проверить делители d от 2 до √n: если у n есть делитель больше корня, то парный ему — меньше корня, и мы его уже нашли.

Алгоритм по шагам

Ввести n.
Если n < 2 — число не простое.
Иначе d = 2; пока d · d ≤ n и n не делится на d — увеличивать d.
Если d · d > n — делителей не нашлось, число простое.

Открыть блок-схему в редакторе

Пример работы

Вход	n = 29
Шаг 1	d = 2: 29 mod 2 = 1
Шаг 2	d = 3: 29 mod 3 = 2
Шаг 3	d = 4: 29 mod 4 = 1
Шаг 4	d = 5: 29 mod 5 = 4
Шаг 5	d = 6: 36 > 29 — цикл закончен, делителей нет
Результат	простое

Решение на Python

n = int(input())
if n < 2:
    print("не простое")
else:
    d = 2
    while d * d <= n and n % d != 0:
        d += 1
    print("простое" if d * d > n else "составное")

Решение на Pascal

var n, d: integer;
begin
  readln(n);
  if n < 2 then writeln('не простое')
  else
  begin
    d := 2;
    while (d * d <= n) and (n mod d <> 0) do
      d := d + 1;
    if d * d > n then writeln('простое')
    else writeln('составное');
  end;
end.

Код блок-схемы

Схема выше нарисована по этому псевдокоду. Скопируйте его в редактор блок-схем или нажмите «Открыть блок-схему в редакторе».

блок-схема: Проверка числа на простоту
начало
ввод n
если n < 2
    вывод «не простое»
иначе
    d = 2
    пока d * d <= n и n mod d ≠ 0
        d = d + 1
    если d * d > n
        вывод «простое»
    иначе
        вывод «составное»
конец

Сложность

O(√n) делений вместо O(n) при переборе всех чисел до n.

Частые ошибки

Считать 1 простым числом — простые начинаются с 2.
Перебирать делители до n − 1: правильно, но в тысячи раз медленнее для больших n.
Условие d · d < n вместо ≤: для n = 25 делитель 5 не будет проверен.