유클리드 호제법

유클리드 호제법은 두수의 최대 공약수를 구하는 알고리즘입니다.

 

1071과 1029의 최대 공약수

1071 MOD 1029 = 42

1029 MOD 42 = 21

42 MOD 21 = 0

최대공약수 = 21

유클리드 호제법의 연산 순서는 다음과 같습니다.

MOD연산은 두 값을 나눈 나머지를 구하는 연산입니다.

1. 큰 수를 작은 수로 나누는 MOD 연산 수행
2. 앞 단계에서의 작은수와 MOD연산 결괏값(나머지)로 MOD 연산 수행
3. 2번을 반복하다가 나머지가 0이 되는 순가의 작은 수를 최대 공약수로 선택