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

Задача

Рассмотрим вариант решения задания из учебника Семакин, Хеннер, Шеина 10 класс, Бином: 15. Найти все простые натуральные числа, не превосходящие n, двоичная запись которых представляет собой палиндром, т. е. читается одинаково слева направо и справа налево. *Цитирирование задания со ссылкой на учебник производится исключительно в учебных целях для лучшего понимания разбора решения задания. 10 semakin10 pract/3-5/zad2/15 98

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

В программе используются две подпрограммы.

Функция dec2bin переводит число из десятичной системы в двоичную:

function dec2bin(x:integer):string;
var s:string;
begin
  s:=»;
  while x>0 do
  begin
    s:=chr(ord(‘0’)+x mod 2)+s;
    x:=x div 2;
  end;
  dec2bin:=s;
end;

Функция palindrom проверяет, является ли число палиндромом в десятичной записи:

function palindrom(var a:integer):integer;
var b,c:integer;
begin
  b:=a;
  c:=0;
  while b>0 do
  begin
    c:=c*10+(b mod 10);
    b:=b div 10;
  end;
  if c=a then palindrom:=1
  else palindrom:=0;
end;

Основная программа перебирает все числа $$k$$ от $$1$$ до $$n$$, считает количество делителей числа $$k$$ и выбирает только простые числа, у которых число делителей равно $$2$$. Затем число переводится в двоичную систему и проверяется, является ли его двоичная запись палиндромом.

Идея решения: вывести все простые числа $$k \le n$$, для которых двоичная запись читается одинаково слева направо и справа налево.

begin
  readln(n);
  for k := 1 to n do begin
    count := 0;
    for i := 1 to k do
      if k mod i = 0 then inc(count);
    if count = 2 then
    begin
      val(dec2bin(k), z, err);
      if palindrom(z)=1 then
        writeln(k);
    end;
  end;
end.

Таким образом, программа находит все простые натуральные числа, не превосходящие $$n$$, двоичная запись которых является палиндромом.