[Algorithm] 최대 공약수, 최소 공배수 구하기

GCD(Greatest Common Divisor) 최대 공약수 구하기

유클리드 호제법 사용

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

a = b x q + r 이라고 했을 때, GCD(a, b) = GCD(b, r)를 만족한다.

간단 증명:

수학적으로 증명하는 방법이 있지만 이해를 위해서 간단히 설명하자면 아래와 같이 표현할 수 있다.

b = r x m + n으로 표현할 때, n이 0이라면 b = rm으로 표현된다. 즉, b와 r의 최대 공약수 GCD(b, r) = m이 된다.

a = bq + r = rmq + r = r(mq + 1) 이므로 GCD(a, b) = r 이다.

=> GCD(a, b) = GCD(b, r) = GCD(r, 0) = r

LCM(Lowest Common Multiple) 최대 공약수 구하기

def lcm(a, b):
    return a // gcd(a, b) * b

a와 b의 최대 공약수 GCD(a, b) = m이라고 했을 때,

a = Am, b = Bm으로 표현 할 수 있다.

이때, 최대 공약수(M) = ABm 이다.

따라서 a % m * b = Am % m * Bm = ABm이 된다.