유클리드 호제법(Euclidean algorithm)으로 최대공약수를 구할 수 있다.
두 정수 m과 n (m>n)의 최대공약수를 구하는 문제를
m-n과 n의 최대공약수를 구하는 문제로 줄일 수 있다.
왜냐하면 m과 n의 최대공약수를 G라 하면 다음과 같이 나타낼 수 있는데
m = Ga
n = Gb
m-n = G(a-b)와 같이 묶을 수 있기 때문이다. (a와 b는 서로소(relatively prime))
예를 들어 94와 30이 있을 경우 아래와 같은 단계를 거쳐 문제를 줄여가면서
최대공약수인 2를 구할 수 있는 것이다.
94 30 (A)
64 30 (A)
34 30 (A)
4 30 (A) (B)
4 26 (B)
4 22 (B)
4 18 (B)
4 14 (B)
4 10 (B)
4 6 (B)
4 2 (B)
2 2
2 0
위 단계에서 (A)부분과 (B)부분을 잘 보면 뺄셈 연산을 여러 번 수행한 결과가 결국 나머지 값이라는 사실을 알 수 있다. 따라서 코드로 작성할 때 나머지연산(%)을 사용하면 다음과 같이 단계를 줄일 수 있다.
94 30
4 30
4 2
2 2
2 0
아래는 C언어로 작성한 코드이다.
int gcd(int n1, int n2)
{
int temp;
if (n1 < n2) {
temp = n1;
n1 = n2;
n2 = temp;
}
while (n2 != 0) {
temp = n1%n2;
n1 = n2;
n2 = temp;
}
return n1;
}
관련글 : 이진 최대공약수 알고리즘 (http://www.tibyte.kr/225)