Работа 3.5 Упр.12 Задание 2 ГДЗ Семакин 10 класс (Информатика)

Задача

Рассмотрим вариант решения задания из учебника Семакин, Хеннер, Шеина 10 класс, Бином: 12. Дано натуральное число n. Найти все меньшие n числа Мерсенна. (Простое число называется числом Мерсенна, если оно может быть представлено в виде 2^p-1, где р — тоже простое число. Например, 31 = 2^5 — 1 — число Мерсенна.) *Цитирирование задания со ссылкой на учебник производится исключительно в учебных целях для лучшего понимания разбора решения задания. 10 semakin10 pract/3-5/zad2/12 98

Подробный ответ

Нужно вывести все числа Мерсенна, меньшие $$n$$. Число Мерсенна имеет вид $$2^p-1$$, где $$p$$ — простое число. Поэтому сначала перебираем числа $$i$$ от $$1$$ до $$n-1$$, проверяем, является ли $$i$$ простым, а затем вычисляем для него число $$2^i-1$$.

Для проверки простоты используется функция Prost: число считается простым, если оно больше $$1$$ и не делится ни на одно число от $$2$$ до $$\sqrt{n}$$.

Для вычисления степени используется функция Step2, которая находит $$2^n$$ последовательным умножением на $$2$$.

const nmax=60;
function Step2(n:byte):extended;
var p:extended;
i:byte;
begin
  p:=1;
  for i:=1 to n do
    p:=p*2;
  Step2:=p;
end;
function Prost(n:longint):boolean;
var i:longint;
begin
  if n<2 then Prost:=false
  else
  begin
    Prost:=true;
    for i:=2 to round(sqrt(n)) do
      if n mod i=0 then
      begin
        Prost:=false;
        break;
      end;
  end;
end;
var n,i:byte;
begin
  repeat
    write(‘Введите число до ‘,nmax,’: ‘);
    readln(n);
  until n in [1..nmax];
  for i:=1 to n-1 do
    if Prost(i) then
      writeln(Step2(i)-1:0:0,’ ‘);
  readln
end.