유클리드 호제법(Euclidean algorithm)

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

 

최대 공약수를 구하기 전에, 먼저 약수란 무엇인지 그 정의를 정확히 알고 갈 필요가 있다.

 

- 약수의 정의

두 수 A, B가 모두 정수일 때, A가 B의 약수라는 말은 B = A * k(k는 정수)라는 말과 동일하다.

즉, A가 B의 약수라는 말은 정수 B가 정수 A로 나누어 떨어진다는 말이다.

 

위와 같은 정의를 이용하면, 그 크기가 작은 수들의 경우 단순 계산으로 손쉽게 최대공약수를 구할 수 있다. 하지만, 두 수의 크기가 커지면 커질수록 단순 계산으로 구하기가 점점 어려워진다. 유클리드 호제법을 이용하면 이러한 큰 수들의 최대공약수도 쉽게 구할 수 있다.

 

<유클리드 호제법의 원리와 증명>

정수 A와 B가 있다고 하자(A > B). 유클리드 호제법에 따르면, A와 B의 최대공약수와 B와 (A % B)의 최대공약수는 같다.

A % B = r이라 하면, gcd(A, B) = g = gcd(B, r) 이라는 이야기이다(gcd는 greatest common devisor의 약자다). 

 

위와 같은 연산을 나머지가 0이 나올때까지 계속 반복하게 되면 gcd(A, B) = gcd(B, r) = gcd(r, B % r) = ... = gcd(G, 0) 와 같은 식이 나오게 된다.

약수의 정의에 따르면 어떤 수 G와 0의 약수는 항상 G이다. 

0 = G * k 일 때, k가 0이 되면 이 식은 항상 만족되므로, G는 0의 약수가 될 수 있기 때문이다.

따라서, A와 B의 최대 공약수는 G가 되게 된다.

 

유클리드 호제법의 핵심은 이와 같이 최대공약수를 구하려는 두 수의 크기를 최대한 줄여 최대공약수를 쉽고 정확하게 구할 수 있게 하는 것이다.

 

유클리드 호제법을 코드로 구현하면 아래와 같다. 코드는 c언어로 작성하였다.

#include <stdio.h>

int main(){
    int num1, num2, gcd;

    scanf("%d %d", &num1, &num2);

    int bigger = num1 > num2 ? num1 : num2; //두 수 중 큰 값을 bigger
    int smaller = num2 > num1 ? num1 : num2; //작은 값을 smaller에 저장. gcd(bigger, smaller) 연산에 필요
    int temp;

    while(smaller > 0){ //나머지가 0이 될 때까지 반복
        temp = bigger;
        bigger = smaller;
        smaller = temp % smaller;
    }
    
    gcd = bigger;

    return 0;
}

 

 

유클리드 호제법의 증명 방법은 다음과 같다.