최대 공약수(GCD)와 최소 공배수(LCM) 관련 알고리즘 팁

프로그래머스 알고리즘 문제에서 최대 공약수, 최소 공배수 관련 문제를 만났는데 이전에 까먹은 관련 알고리즘을 까먹지 않기 위해서!

기록하고자 한다! (파이썬 기준)

GCD(greatest common divisor)

두 수의 최대 공약수를 의미하고

LCM(Largest Common Multiple)

두 수의 최소 공배수를 의미한다.

유클리드 알고리즘

두 수의 최대 공약수를 구하는 알고리즘이다.

2 개의 자연수 a,b에 대해 a> b 일때, a % b == r 라고 한다면 (r > 0),

a 와 b의 최대공약수 == r과 b의 최대공약수 이다.

이를 이용해서 b % r == r' 일때

r % r' == xxx.... 이렇게 반복하다가 나머지가 0 일때 나누는 수가 a 와 b의 최대공약수다.

최대 공약수를 이용하면 최소 공배수도 구할 수 있다.

최소공배수 == (a*b)//최대 공약수
LCM = GCD * (a//GCD) * (b//GCD) -> (a*b) // GCD 이기 때문이다.

코드

def gcd(a,b):
    if b == 0:
    	return a
    if a % b == 0:
    	return b
    else:
    	return gcd(b, a % b)
a = 8
b = 6
lcm = (a*b) // gcd(a,b) #24