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

Привет! Сегоднчя мы решаем интересную и достаточно сложную задачу на языке программирования Leo от проекта Aleo. Полный текст задачи выглядит так:

Давайте начнем с изучения алгоритма поиска наименьшего общего кратного (далее НОК):

Открываем Aleo Studio и создаем новый проект.

У нас создалась базовая программа, изменяем вход и выход функции main. На входе две переменные типа u32, НОК которых мы и будем находить. На выходе функции переменная также типа u32, она будет хранить в себе НОК.

Для начала находим наибольший общий делитель (далее НОД) с помощью алгоритма, указанного ранее. Создаем вспомогательную переменную ost в которой будет храниться остаток от деления большего числа на меньшее.

Теперь создаем цикл for с помощью которого будем делать перебор. В идеале было бы использовать цикл while, но Leo его пока не поддерживает.

Следующим шагом добавляем условия проверки, является ли остаток равным нулю и также у нас появляются два случая: когда a > b и когда b > a.

В каждом случае прописываем нахождение остатка деления большей переменной на меньшую и записываем это значение в переменную ost.

Теперь нам нужно найти остаток от деления меньшей переменной на остаток.

Здесь появляется нюанс, что нам нужно хранить последнее значение остатка, который не равен 0, для этого мы создаем вспомогательную переменную и в неё сохраняем остаток до нахождения остатка от деления меньшего числа на предыдущий остаток

Самое сложное мы сделали, теперь в переменной l_ost хранится НОД чисел. Создадим переменную nok в которую сохраним результат работы программы, а также переменную mult в которой будет хранится перемноженное значение переменных a и b (она требуется при нахождении НОК, используя НОД).

Осталось в переменную nod записать формулу и вывести её по результату работы программы. Итоговый код выглядит так:

transition main(a: u32, b:u32) -> u32 {
        let ost: u32 = 0u32;
        let l_ost: u32 = 0u32;
        let nok: u32 = 0u32;
        let mult: u32 = a*b;
            for i: u32 in 1u32..10u32 {
                if b != 0u32 {
                    if a > b {
                        ost = a.rem(b);
                        l_ost = ost;
                        ost = b.rem(ost);
                    }
                    if b > a {
                        ost = b.rem(a);
                        l_ost = ost;
                        ost = a.rem(ost);
                    }
                }
            }
            nok = mult / l_ost;
            return nok;
    }

Давайте проверим наш код с этими входными данными:

Мы должны получить 60. Запускаем нашу программу:

Всё верно, наша программа работает корректно. До встречи в следующих статьях!