유클리드 호제법

유클리드 호제법은 두 수의 최대 공약수를 구하는 알고리즘
일반적으로 최대 공약수를 구하는 방법은 소인수 분해를 이용한 공통된 소수들의 곱으로 표현할 수 있지만 유클리드 호제법은 좀 더 간단한 방법을 제시합니다.

유클리드 호제법의 핵심 이론
MOD 연산을 이해하고 있어야 한다 MOD 연산이 최대 공약수를 구하는 데 사용하는 핵심 연산
10 MOD 4 = 2 # 10 % 4 = 2

1. 큰 수를 작은 수로 나누는 MOD 연산을 수행한다.
2. 앞 단계에서의 작은 수와 MOD 연산 결괏값(나머지)으로 MOD 연산을 수행한다.
3. 나머지가 0이 되는 순간의 작은 수를 최대 공약수로 선택한다.
   *일반적으로 최대 공약수를 구하는 연산은 gcd로 정의
   270과 192의 최대 공약수

나머지가 0이 될 때까지 반복
gcd(270,192)
270 % 192 = 78
192 % 78 = 36
78 % 36 = 6
36 % 6 = 0
0이 나오면 36과 6 둘 중 작은 수 6이 최대 공약수가 된다
gcd(270,192) = 6