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

Задача

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

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

Нужно вывести все числа Мерсенна, меньшие $$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.