[Algorithm] 재귀를 이용하여 최대공약수 구하기

안녕하세요, Einere입니다.

(ADblock을 꺼주시면 감사하겠습니다.)

---

오늘은 재귀(recursion)을 이용하여 최대공약수(greatest common divisor)를 구하는 방법을 알아보도록 하겠습니다.

 

 

 

최대공약수와 유클리드 호제

2개 이상의 수의 공약수 중에서 최대인 수이다.
이를 테면, 18의 약수는 1, 2, 3, 6, 9, 18 이고,12의 약수는 1, 2, 3, 4, 6, 12 로서 6이 최대공약수이며, 이것을 (12,18)＝6으로 쓴다. 다른 공약수는 모두 6의 약수이다.
최대공약수를 구하는 방법은, 우선 소인수(素因數)로 분해하여 공통의 수를 택하여 곱해주면 된다. 예를 들면 (12,18)을 구할 경우 12＝22×3, 18＝2×32이므로 (12,18)＝2×3＝6이 된다.
또, 주어진 수가 커서 소인수분해하기 곤란할 때에는 유클리드의 호제법을 이용하는 것이 더 간편하다. 두 수 A,B의 최대공약수를 G, 또 A,B를 각각 G로 나누었을 때의 몫을 a,b라 하면, A＝aG, B＝bG인 관계가 성립한다. 이 때 a, b는 서로 소(素), 즉 (a,b)＝1이다. 또 A,B의 최소공배수가 L이면, LG＝AB인 관계가 성립한다.
세 수의 경우 (A,B,C)＝((A,B),C), 즉 두 수의 최대공약수와 나머지 한 수의 최대공약수를 구하면 결국 세 수의 최대공약수가 된다.
네 수 이상에서도 마찬가지로 생각할 수가 있다. 최소공배수에서도 ［A,B,C］＝［［A,B］,C］가 성립한다. [네이버 지식백과] 최대공약수 [Greatest common divisor, 最大公約數] (두산백과)

두산백과에서는 위와 같이 나옵니다.

여기서 중요한 부분은 유클리드 호제법입니다.

간단히 말하자면, "두 양의 정수 A >= B에 대해, A가 B의 배수인 경우에 최대공약수는 B이며, 그렇지 않은 경우에는 최대공약수는 B와 A%B의 최대공약수이다."라고 할 수 있습니다.

코드로 표현하자면 다음과 같습니다.

public int gcd(int m, int n){
    // m >= n을 보장하기 위해 스왑합니다.
    if(m < n) {
        int tmp = m;
        m = n;
        n = m;
    }
    if(m%n == 0) return n;
    else return gcd(n, m%n);
}

 

좀 더 간단한 버전은 다음과 같습니다.

public int gcd(int m, int n){
    if(n == 0) return m;
    else return gcd(n, m%n);
}

참고로, 위 코드는 m >= n이어야 하는 조건이 필요가 없습니다.