Наименьшее общее кратное пар чисел

Задача

Найти наименьшее общее кратное (НОК) пар целых положительных чисел через наибольший общий делитель (НОД) по формуле lcm = ab / gcd(a; b), где lcm - НОК, gcd - НОД, a и b - числа.

Решение

 

В основной ветке программы запрашиваются два числа, которые передаются в функцию, вычисляющую и возвращающую НОК.

В самой функции переменная, которой присваивается произведение переданных значений, имеет тип longint, т.к. диапазона ни integer, ни даже word может быть недостаточно.

Произведение следует найти до того, как будет найден НОД, т.к. в процессе его вычисления значения переменных-чисел уменьшается. НОД содержится в одной переменной-числе, но поскольку вторая в любом случае содержит 0, и мы не знаем, какая что именно содержит, то проще их сложить.

Программа на языке Паскаль: 

 

var a, b: word;
 
function lcm(c, d: word): word;
    var mult: longint;
    begin
        mult := c * d;
        while (c <> 0) and (d <> 0) do
            if c > d then
                c := c mod d
            else
                d := d mod c;
        lcm := mult div (c + d);
    end;
 
begin
    repeat
        write('Two numbers: ');
        readln(a,b);
        if (a = 0) and (b = 0) then break;
        writeln('LCM: ', lcm(a,b));
    until (a = 0) and (b = 0);
end.

 

Пример выполнения программы:

Two numbers: 800 899
LCM: 63840
Two numbers: 15 16
LCM: 240
Two numbers: 121 212
LCM: 25652
Two numbers: 25 30
LCM: 150
Two numbers: 0 0

 

Тема

Процедуры, функции, рекурсии

Уровень

Комбинированные задачи