유클리드 호제법 - 최대공약수 구하는 알고리즘, 최소공배수

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

최소공배수는 두 수를 곱한 뒤 최대공약수로 나눠서 구할 수 있다.

예를 들어 18과 24의 최대공약수는 6이고 각각 6x3, 6x4로 나타낼 수 있다. 최소공배수는 6x3x4이므로, 18과 24를 곱한 뒤 최대공약수로 한 번 나눠주면 된다.

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

최소공배수 = a*b // gcd(a, b)