자료구조+알고리즘

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

덕구공 2022. 3. 29. 17:50

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)