Наименьшее общее кратное

Найти наименьшее общее кратное (НОК) пары чисел по формуле

НОК = ab / НОД(a, b),

где a и b - это натуральные числа, НОД - наибольший общий делитель.

Из условия задачи ясно, чтобы найти НОК, надо сначала найти НОД. Последний можно вычислить, постепенно находя остаток от деления большего числа из пары на меньшее и присваивая остаток переменной, связанной с большим числом (см. алгоритм Евклида). В какой-то момент значение одной из переменных станет равным 0. Когда это произойдет, другая будет содержать НОД. Если неизвестно, какая именно переменная содержит НОД, то можно просто сложить значения обоих переменных.

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

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

def lcm(a, b):
    m = a * b
    while a != 0 and b != 0:
        if a > b:
            a %= b
        else:
            b %= a
    return m // (a + b)
 
 
while 1:
    try:
        x = int(input('a = '))
        y = int(input('b = '))
        print('НОК:', lcm(x, y))
    except ValueError:
        break

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

a = 14
b = 18
НОК: 126
a = 105
b = 305
НОК: 6405
a = stop

В модуле math языка программирования Python есть функция для нахождения наибольшего общего делителя (gcd - greatest common devisor). При ее использовании наша функция вычисления наименьшего общего кратного lcm (least common multiple) упрощается.

def lcm(a, b):
    import math
    return (a * b) // math.gcd(a, b)

Решение задач на Python