[알고리즘 in python] 최대공약수 / 최소공배수 - 유클리드 호제법

유클리드 호제법 (Euclidean Algorithm) / 최대공약수 계산

• 두 정수의 최대공약수 (GCD, Greatest Common Divisor)를 효율적으로 계산하는 알고리즘
• 두 수의 최대공약수가 두 수의 차이의 최대공약수와 같다는 것

원리

두 정수 $a$와 $b$ $(a>b)$의 최대공약수를 구하기 위해 다음 과정을 반복

1. $a$를 $b$로 나눈 나머지 $r$을 구한다.
2. $a$를 $b$로, $b$를 $r$로 대체한다.
3. $r$이 0이 될 때까지 이 과정을 반복한다.
4. $r$이 0이 되었을 때, $b$가 $a$와 $b$의 최대공약수

$$ GCD(a,b)=GCD(b,a\bmod b)$$

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

• 시간복잡도는 $O(log\ min(a,b))$ 를 가진다.

---

최소공배수 (LCM, Least Common Multiple)

• 최대공약수를 이용해 구하기
• 두 수의 곱을 최대공약수로 나눈 값 = 최소공배수

$$
\text{LCM}(a, b) = \frac{|a \times b|}{\text{GCD}(a, b)}

$$

원리

1. 두 수 $a$와 $b$의 최대공약수(GCD)를 유클리드 호제법을 사용하여 구함
2. 두 수 $a$와 $b$의 곱을 계산
3. 두 수의 곱을 최대공약수로 나눔
4. 나눈 결과가 최소공배수 (LCM)

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

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