НОД (алгоритм Евклида)

Алгоритм Евклида находит наибольший общий делитель двух чисел, многократно заменяя большее число на остаток от деления: gcd(a, b) = gcd(b, a mod b), пока второе не станет нулём.

Сложность: время O(log(min(a, b))); память O(1) для итеративной версии. На основе НОД легко получить наименьшее общее кратное: lcm = a * b // gcd(a, b).

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

print(gcd(48, 36))  # 12