ГДЗ по информатике 11 класс Босова, номер §7 ПМ 1

§ ПМ Проверка простоты числа

Усовершенствуйте приведённую выше программу с учётом этих соображений. В программе проверяется, является ли заданное натуральное число $n\geqslant2$ простым: последовательно перебираются его возможные делители от 2 до $n-1$ . Учтите, что если $n=a\cdot b$ , то хотя бы одно из чисел $a$ , $b$ не больше $\sqrt n$ .

Решение

Если составное число представимо в виде произведения , то оба множителя не могут быть больше : иначе их произведение было бы больше . Поэтому достаточно проверять делители, квадрат которых не превышает . Как только найден делитель, дальнейший перебор не нужен.

var
  n, i: longint;
  flag: boolean;
begin
  write('Введите n (n >= ): ');
  read(n);
  i := ;
  flag := true;
  while (i <= n div i) and flag do
  begin
    if n mod i =  then
      flag := false
    else
      i := i + 
  end;
  if flag then writeln('Да')
  else writeln('Нет')
end.

Переменная flag сначала имеет значение true: делитель ещё не обнаружен. Переменная i получает значение , потому что единица делит любое натуральное число и не позволяет определить простоту. При положительном i проверка i <= n div i равносильна проверке , но при этом не требуется вычислять квадрат, который мог бы выйти за пределы типа longint. Так перебираются только делители не больше . Операция n mod i даёт остаток: если он равен нулю, число делится на i, поэтому flag становится false; иначе переходим к следующему кандидату.

Например, для проверяются : остатки равны соответственно . При условие ложно, поэтому программа выведет «Да». Для при остаток , и программа выведет «Нет». Значит, проверка всех чисел до не требуется.

Ответ

Программа перебирает делители только при i <= n div i и выводит «Да» для простого числа, «Нет» для составного.

Помогло?

Номер §7 ПМ 1