Hosted by uCoz

Задача № 36. Найти наименьший нетривиальный делитель двух заданных чисел

Формулировка. Даны натуральные числа m и n. Вывести на экран их наименьший нетривиальный делитель или сообщить, что его нет.

Решение. Задача похожа на задачу 15, в которой поиск минимального делителя осуществлялся с помощью цикла:

for i := 2 to n do begin

  if n mod i = 0 then begin

    writeln(i);

    break

  end

end;

Здесь все просто: проверяем все числа от 2 по возрастанию – если нашли делитель, выводим его на экран и выходим из цикла с помощью break. В нашем же случае нужно проверять делимость двух введенных чисел. При этом цикл должен проходить по всем i от 2 до минимального из чисел m и n (назовем его min), так как оно может быть наименьшим нетривиальным делителем, когда оно простое. Например, для чисел 17 и 34 таковым является 17.

Найти наименьшее из двух чисел можно так:

if n < m then min := n else min := m;

Кстати, теперь в цикле мы должны не просто вывести на экран найденный делитель, а сохранить его в некоторую переменную (mindiv), которая до входа в цикл будет равна 1 (или 0), чтобы проверить, выполнилось ли условие делимости в цикле. Если да, то необходимо вывести значение наименьшего общего делителя, а если нет, и mindiv все еще равно 1 (или 0), то вывести сообщение об отсутствии делителя.

Код:

  1. program MinDivisor;
  2. var
  3. m, n, i, min, mindiv: word;
  4. begin
  5. readln(m, n);
  6. mindiv := 1;
  7. if n < m then min := n else min := m;
  8. for i := 2 to min do begin
  9. if (n mod i = 0) and (m mod i = 0) then begin
  10. mindiv := i;
  11. break
  12. end
  13. end;
  14. if mindiv <> 1 then writeln(mindiv) else writeln('No divisors!')
  15. end.