GCD, LCM 구하기

1. GCD (Greatest Common Divisor)

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

이 방법은 유클리드 호제법을 기반으로 한다. b와 b로 a를 나눈 나머지를 인자로 주며 재귀호출하다가 b가 0이면 a를 반환한다. a로 나눠도 상관없는데 이 경우의 코드는 아래와 같다.

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

2. LCM (Least Common Multiple)

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

최소공배수는 두 수의 곱에서 최대공약수를 나눈 것과 같다. 위 코드는 이 성질을 이용한다.