유클리드 호제법

유클리드 호제법은 두 수의 최대공약수를 구하는 알고리즘입니다. 이 알고리즘은 두 수를 나눈 나머지를 이용해 최대공약수를 구하는 방법입니다.

먼저, 큰 수를 작은 수로 나눈 나머지를 구합니다. 그리고, 작은 수를 이전에 구한 나머지로 나눈 나머지를 구합니다. 이 과정을 나머지가 0이 될 때까지 반복합니다. 마지막으로 구한 나머지가 최대공약수가 됩니다.

[백준] 2608번 - 최대공약수와 최소공배수

# 최대공약수(유클리드 호제법)
def gcd(a, b):
    while b > 0:
        a, b = b, a % b
    return a

# 최소공배수(두 수를 곱하여 최대공약수로 나누면 된다.)
def lcm(a, b):
    return a * b // gcd(a, b)