[ 정수론 ] 최대공약수 구하기 - 유클리드 호제법

 

유클리드 호제법이란?

 

두 양의 정수의 최대공약수를 구하는 알고리즘 중 하나로,
두 수가 반복적으로 서로 나누어지면서, 나머지를 구하며 최대공약수를 얻게 된다.

---

유클리드 호제법의 기본 원리

 

📝 A,B의 최대공약수 = A-B, B의 최대공약수

A, B의 최대공약수와 A-B, B의 최대공약수는 같다.

* GCD : 최대 공약수( Greatest Common Divisor )

아하 ! 그러면 A, B의 최대공약수를 구하는 대신, A-B, B를 이용하면 빠르겠군 !

그런데 A와 B의 차가 크다면 ...?
가령, 1024와 2라고 해보자.

GCD (1024, 2)
GCD (1022, 2)
GCD (1020, 2)
GCD (1018, 2)
.
.
.
GCD (2, 2)

이걸 어느 세월에....ㅜ
그래서 나온 또 다른 증명 !

 

 

📝 A,B의 최대공약수 = A%B, B의 최대공약수

A, B의 최대공약수와 A%B, B의 최대공약수는 같다.

 

위에서 증명했듯 "A, B의 최대공약수"와 "A%B, B의 최대공약수"가 같으므로,
두 수를 나눈 나머지를 활용하면 최대공약수를 빠르게 구할 수 있다.

이러한 원리에 기반한 알고리즘이 바로 유클리드 호제법이다.

 

---

 

알고리즘

 

유클리드 호제법의 알고리즘은 다음과 같다.
위에서 증명한 GCD(A%B, B) = GCD(A, B) 인 점을 활용하는 것이다.

A, B의 최대공약수를 구하려한다. ( A>B>0 )

1) A%B를 B자리에, B를 A자리에 넣고 반복합니다. ( A%B < B )
2) 작은 수인 B가 0이 될때까지 위의 과정을 반복한다. 
3) B가 0이 되었을 때, A 자리에 있는 수가 두 수의 최대공약수이다.

 

숫자로 예시를 들어보면, 4와 18의 최대공약수를 구해보자.

GCD(18, 4) = GCD(4, 2) = GCD(2, 0)
이런식으로 나머지연산과 스왑을 반복하면 두 수의 최대공약수가 2라는 것을 구할 수 있다.

 

 

---

구현

 

그럼 유클리드 호제법으로 최대공약수를 구하는 c++ 코드를 작성해보자.

주로 재귀를 사용하고, 반복문으로도 구현이 가능하다 :)

// 재귀
int gcd_recursive(int a, int b) {
    if (b == 0) {
        return a; // b가 0이면, a가 최대공약수 !
    }
    return gcd_recursive(b, a % b);
}

// 반복문
int gcd_iterative(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a; // b가 0이면, a가 최대공약수 !
}