Найти наименьшее общее кратное двух натуральных чисел

Формулировка. Даны два натуральных числа. Найти их наименьшее общее кратное.

Примечание: наименьшим общим кратным двух чисел m и n называется наименьшее натуральное число, которое делится на m и n. Обозначение: НОК(m, n)

Решение. Из теории чисел известно, что НОК(m, n) связан с НОД(m, n) следующим образом:

Следовательно, для нахождения ответа нам нужно лишь использовать предыдущую задачу нахождения НОД двух чисел m иn:

while m <> n do begin

if m > n then begin

m := m — n

end

else begin

n := n — m

end

end;

Так как исходные переменные будут испорчены в процессе работы алгоритма Евклида, нам нужно вычислить их произведение до входа в описанный выше цикл и присвоить это произведение переменной prod (от англ. product – «произведение»):

prod := m * n;

После этого нам остается вывести на экран результат арифметического выражения в правой части нашей формулы. В качестве самого НОД будет использоваться переменная m:

writeln(prod div m);

Кстати, деление в формуле будет целочисленным (через div) именно потому, что если два числа делятся на некоторое число, то и их произведение также делится на него.

Код:

  1. program LeastCommonMult;
  2. var
  3. m, n, prod: word;
  4. begin
  5. readln(m, n);
  6. prod := m * n;
  7. while m <> n do begin
  8. if m > n then begin
  9. m := m — n
  10. end
  11. else begin
  12. n := n — m
  13. end
  14. end;
  15. writeln(prod div m)
  16. end.