유클리드 호제법, 최대공약수

유클리드 호제법

최대공약수를 구하기 위한 방법입니다.

최대 공약수 구하기

1. 큰수에서 작은수로 MOD연산 실행
2. 전단계의 작은 수를 큰수로 연산 결과로 다시 설정
3. MOD 연산의 결괏값이 0이 나오면 그 연산의 작은 수를 최대 공약수로 선택

270 % 192 = 78
192 % 78 = 36
78 % 36 = 6
36 % 6 = 0
gcd(270, 192) = 6