최대공약수(GCD) / 최소공배수(LCD)

GCD

• 유클리드 호제법을 이용해서 간단히 구할 수 있다.
• 숫자 a와 b가 있을 때, a를 b로 나눈 나머지와 b 의 최대공약수 는 a와 b의 최대공약수가 같다는 것을 의미한다.

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

LCD

• 두 수 a와 b가 있을 때 a와 b를 곱한 값에서 a와 b의 최대공약수를 나누면 된다!

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