Формулировка. Даны два натуральных числа. Найти их наименьшее общее кратное.
Примечание: наименьшим общим кратным двух чисел 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) именно потому, что если два числа делятся на некоторое число, то и их произведение также делится на него.
Код:
- program LeastCommonMult;
- var
- m, n, prod: word;
- begin
- readln(m, n);
- prod := m * n;
- while m <> n do begin
- if m > n then begin
- m := m — n
- end
- else begin
- n := n — m
- end
- end;
- writeln(prod div m)
- end.