유클리드 호제법(최대공약수), 최소공배수

코딩테스트에서 종종 나오는 정수론 문제 관련한 코드를 정리해보고자 한다.

 

유클리드 호제법에 대한 설명

https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95

유클리드 호제법 - 위키백과, 우리 모두의 백과사전

 

* Greatest common divisor(gcd)

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

* Least common multiple(lcm)

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

 

사실 둘다 python math 라이브러리에 구현이 되어있다.

import math
a, b = 6, 15
print(math.lcm(a, b))
print(math.gcd(a,b))

#output
#30
#3