BOJ 2609 최대공약수와 최소공배수 BOJ 1934 최소공배수 (유클리드 호제법)

유클리드 호제법(Euclidean Algorihtm)

두 수의 최대공약수를 구하는 알고리즘. 나머지가 0이 될 때까지 서로의 나머지를 재귀적으로 구한다. 코드는 간단하다.

# 최대공약수
def euclidean_algo(n: int, m: int):
    if m == 0:
        return n
    return euclidean_algo(m, n % m)

최소공배수는 두 수의 곱을 최대공약수로 나누면 되므로 호제법만 기억하자.

# 최소공배수
n * m // euclidean(n, m)