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

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

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

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

Решение задачи на языке программирования Python

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

Больше задач в PDF