§ 13. Пример задачи на сочетание оператора цикла и условного оператора

задача 4

Требуется составить программу определения наибольшего общего делителя (НОД) двух натуральных чисел.

Решение

Одним из простейших алгоритмов нахождения наибольшего общего делителя является Алгоритм Евклида. Идея этого алгоритма основана на том свойстве, что если `M>N`, то  `"НОД"(M, N)="НОД"(M-N, N)`.

Иначе говоря, НОД двух натуральных чисел равен НОД их положительной разности (модуля их разности) и меньшего числа.

var M, N: integer;
begin
     writeln('Введите М и N');
     readln(M, N);
     while M<>N do
          begin
               if M>N
               then M:=M-N
               else N:=N-M
     end;
     write('Н0Д=',М)
end.