최소 공배수는 최대 공약수를 통해 구할 수 있고
최대 공약수를 구하는 방법으로는 많이들 유클리드 호제법을 제시한다.
(볼때 마다 까먹어서 나오면 구글링함,,)
유클리드 호제법은 mod(%) 연산을 반복 수행하여 나머지가 0이 될때 나누는 수가 최대 공약수가 된다.
최소 공배수는 구하는 두 수의 곱을 최대 공약수로 나누면 도출된다
간단한 증명
G = 최대공약수 & a = Gx & b = Gy 일때 (x,y 는 정수)
a * b = GGxy a * b / G = GGxy / G a * b / G = Gxy 최소공배수 = a * b / G
코드로 풀면 다음과 같이 구현할 수 있다.
def gcd(a, b):
while b > 0:
a, b = b, a % b
return a
def lcm(a, b):
return a * b // gcd(a, b)
*출처