유클리드 호제법

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

 

 

유클리드 호제법의 핵심 이론

유클리드 호제법을 수행하려면 먼저 MOD 연산을 이해하고 있어야 한다. MOD 연산이 최대 공약수를 구하는데 사용되는 핵심 연산이기 때문이다.

연산	기능	예제
MOD	두 값을 나눈 나머지를 구하는 연산	10 MOD 4 = 2 // 10 % 4 = 2

 

MOD 연산으로 구현하는 유클리드 호제법

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