[알고리즘] 유클리드 호제법 Euclidean algorithm

최대공약수(GCD, Greastest Common Divisor)

---

숫자 A, B가 있을 때 A의 약수와 B의 약수 중 공통인 약수들이 있다.
그 중 최대 약수가 최대공약수이다.

x = 8
y = 10

>>> x와 y의 약수
x : [1, 2, 4, 8]
y : [1, 2, 5, 10]

>>> x와 y의 공통 약수
[1, 2]

>>> x와 y의 최대공약수
2

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

---

숫자 A, B가 있을 때 A의 배수와 B의 배수 중 공통인 배수들이 있다.
그 중 최소 배수가 최소공배수이다.

x = 10
y = 12

>>> x와 y의 배수
x : [10, 20, 30, 40, 50, 60, 70, ...]
y : [12, 24, 36, 48, 60, 72, ...]

>>> x와 y의 공통 배수
[60, 120, ...]

>>> x와 y의 최소공배수
60

일반적인 최대공약수와 최소공배수 구하기

---

직관적으로 for문을 통해서 소인수분해를 할 수 있다.

a = 10
b = 12

# 최대공약수 구하기
for i in range(min(a, b), 0, -1):
	if a % i == 0 and b % i == 0:
    	print(i)
        break
        
# 최소공배수 구하기
for i in range(max(a, b), (a*b) + 1):
	if i % a == 0 and b % i == 0:
    	print(i)
        break

1. 최대공약수 구하기
   최대공약수는 a, b 중 작은 값보다 큰 값이 나올 수 없다.
   그래서 두 수 중에서 작은 값에서 시작해서 0까지 1씩 줄여가며 조건을 걸어 확인해보면 된다.
   
   만약 그 값으로 a, b를 나눴을 때 나머지가 0이라면 두 수의 약수라는 것을 확인할 수 있고, 큰 값에서 줄여가며 확인하고 있기 때문에 해당 조건에 처음으로 일치하는 값이 최대공약수가 된다.
   
   
2. 최소공배수 구하기
   최소공배수는 a, b 중 큰 값을 기준으로 a*b 값까지 1씩 증가시키며 조건을 걸어 확인할 수 있다.
   
   만약 그 값을 a, b로 나눴을 때 나머지가 0이라면 두 수의 공통인 배수라는 것이고, 작은 값에서 증가를 하며 확인하고 있기 때문에 해당 조건에 처음으로 일치하는 값이 최소공배수가 된다.

유클리드 호제법 Euclidean Algorithm

---

유클리드 호제법이 말하는 바는 다음과 같다.

a, b의 최대공약수는 b, r의 최대공약수와 같다.(이때 r = a % b이다.)
GCD(a, b) = GCD(b, r = a % b)

위의 예시인 a = 10, b = 12일 때를 생각해보면 다음 표와 같다.
r = 0가 되었을 때의 b값이 최대공약수가 된다.

GCD(a, b)	a	b	r
GCD(10, 12)	10	12	10
GCD(12, 10)	12	10	2
GCD(10, 2)	10	2	0

이를 코드로 구현하면 다음과 같다.

최대공약수는 위 공식으로 구할 수 있고,
최소공배수는 두 수의 곱을 두 수의 최대공약수로 나눠주면 된다.

def GCD(a, b):
    while b:
        a, b = b, a % b
    return a
    
>>> GCD(10, 12)
2
    
def LCM(a, b):
    result = (a * b) // GCD(a, b)
    return result

>>> LCM(10, 12)
60