[Algorithm] 유클리드 호제법 | Euclidean Algorithm

---

유클리드 호제법 | Euclidean Alogrithm

2개의 자연수 x, y가 주어질 때 x, y의 최대공약수를 구하는 알고리즘
GCD(x, y)를 구한 후 LCM(x, y)도 응용해 구할 수 있다.

---

👉🏻 GCD(x, y) | 최대공약수

두 수(x, y)를 소인수분해한 뒤, 두 수의 공통된 소인수를 모두 곱한 값

• x, y = 자연수 x, y
• r = x % y
  x, y의 최대공약수 == y, r의 최대공약수
  x, y의 최대공약수는 y, r의 최대공약수와 같다.

x % y == 0이 될 때까지,
x→y를 대입 & y→r(:x%y)를 대입해 최종 y의 값이 최대공약수가 된다.

👉🏻 LCM(x, y) | 최소공배수

두 수(x, y)를 소인수분해한 뒤, 두 수의 모든 소인수를 곱한 값
x*y // GCD(x, y)

---

ex)
x = 10, y = 12 일 때 두 수의 GCD와 LCM을 구하시오.

GCD(x, y)   = 10(x)    %  12(y)  == 10(r)
		    = 12 (x→y) % 10(y→r) == 2(r)
            = 10(x→y)  % 2(y→r)  == 5
GCD(10, 12) = 2

• x = 10, y = 12, r = 10
• x = 12 (x에 y를 대입), y = 10(y에 r을 대입), r = 2(x%y 대입)
• x = 10(x에 y를 대입), y = 2(y에 r을 대입), r = 5(x%y 대입)

LCM(x, y) 	= (x * y) // GCD(x, y)
		  	= (10*12) // 2
LCM(10, 12) = 60