최대공약수(GCD) 와 최소공배수(LCM)

Problem Solving 의 정수론 분야 중 두 수의 최대공약수와 최소공배수를 이용한 문제들은 매우 자주 등장하는 편이다.
구하는 방법은 여러가지가 있는데...


방법 1) 소인수 분해 (Prime Factorization)
중학교 때 배우게 되는 소인수 분해를 이용한다
어떤 수의 모든 소인수를 구하는 방법은 소수구하기 알고리즘을 이용한다.

소인수분해는, a 와 b 를 소수로 나눌 수 있는 만큼 인수분해하여, 최대공약수는 두 수의 공통된 소인수들 중에서 차수가 최소인 값들의 곱이 되며, 최소공배수는 두 수의 모든 소인수들 중에서 차수가 최대인 값들의 곱이 된다.

#include <iostream> #include <algorithm> #include <vector> #include <cmath> #include <set> using namespace std; int prime[1000]; bool isprime(int n) { if( n <= 2 ) return true; if( n%2 == 0 ) return false; for( int a = 3; a*a <= n; a++ ) if( n%a == 0 ) return false; return true; } int main() { int a, b, i, n, cnt, tmp, lcm = 1, gcd = 1; vector<pair<int,int> > prime1, prime2; for( i = 2; i < 10000; i++ ) if( isprime(i) ) prime2.push_back(make_pair(i,0)); prime1 = prime2; cin >> a >> b; tmp = a, cnt = 0; while(tmp > 1) { n = prime1[cnt].first; while( tmp%n == 0 ) { tmp /= n; prime1[cnt].second++; } cnt++; } tmp = b, cnt = 0; while(tmp > 1) { n = prime2[cnt].first; while( tmp%n == 0 ) { tmp /= n; prime2[cnt].second++; } cnt++; } for( i = 0; i < prime1.size(); i++ ) { if( prime1[i].second > 0 && prime2[i].second > 0 ) { n = min( prime1[i].second, prime2[i].second ); gcd *= (int) pow((double) prime1[i].first, (double)n); } if( prime1[i].second > 0 || prime2[i].second > 0 ) { n = max( prime1[i].second, prime2[i].second ); lcm *= (int) pow((double) prime1[i].first, (double)n); } } cout << gcd << " " << lcm << endl; return 0; }
이 방법은 수학시간에 배운 직관적인 방법이고, 많은 이들에게 익숙하지만 위에서 보듯이 코딩으로 옮기기에는 꽤나 귀찮다는 단점이 있다. 또한 두 수 a, b 의 모든 소인수를 구해서 저장해 놓아야 하므로 별도의 메모리를 필요로 한다. ( 위의 코드는 10000 까지의 소인수에 대해서 구현한 코드 )


방법 2) Brute force
최대공약수의 정의를 이용하여, brute force 방법으로 직접 구한다.
즉, 두 수 a, b 를 나누어서 나머지가 0 이 되는 수들 중에서 가장 큰 숫자를 구하면 이 숫자가 최대공약수가 되며, 두 수 a, b 의 배수를 구하여 공통된 배수 중 가장 작은 숫자를 구하면 이 숫자가 최소공배수가 된다.
int main() { int a, b, i; cin >> a >> b; int n = min(a,b); int m = max(a,b); for( i = n; i >= 1; i-- ) if( a%i == 0 && b%i == 0 ) break; cout << "gcd = " << i << endl; for( i = m; i <= a*b; i++ ) if( i%a == 0 && i%b == 0 ) break; cout << "lcm = " << i << endl; return 0; }
위의 코드에서 만약 a, b 간의 공약수가 존재하지 않는 경우는 두 수의 최대공약수는 자연스럽게 1이 되며, a, b 간의 최소공배수 중 가장 클 가능성이 있는 수는 a*b 가 되므로 a*b 까지만 검사를 하면 된다.

이 방법은 최대 a*b 번의 연산을 해야 하므로,  a 와 b 가 커질수록 수행시간이 급격히 늘어난다.


방법 3) Euclid's algorithm - Using Recursion
사실 최대공약수와 최소공배수를 구하는 것은 고대 그리스의 수학자, 유클리드가 고안한 "유클리드 알고리즘"(Euclid's algorithm) 을 쓰면 간결하게 해결할 수 있다. 이 방법은 The Art Of Computer Programming 의 제 1장에도 소개된 바 있다.
a, b 중 큰 수를 a, 작은 수를 b 라 하자. 이 두 수의 최대공약수를 구하려면 a 를 b 로 나눈다. 이 연산을 한 후에 b 와 a%b 를 갖고 어느 한쪽이 0 이 될때까지 이 과정을 계속 반복한다. a%b 가 0 이 될 때의 b 가 바로 최대공약수가 된다. 이를 코드로 옮기면 다음과 같다.
int recursion(int a, int b) { if ( a%b == 0 ) return b; else return recursion(b, a%b); } int main() { int a, b; cin >> a >> b; int gcd = recursion(a,b); cout << "gcd = " << gcd << endl; cout << "lcm = " << (a*b)/gcd << endl; return 0; }

최대공약수와 최소공배수의 성질을 이용하면 아래와 같이
최소공배수 = (a*b) / 최대공약수
최대공약수 = (a*b) / 최소공배수
가 되므로, 최대공약수나 최소공배수 둘 중 하나만 구하면 나머지 하나는 쉽게 구할 수 있다.


방법 4) Euclid's algorithm - Using Iteration
방법 3 은 매우 간결한 코딩이 가능하지만, 재귀호출을 이용한다는 단점이 있다. 재귀호출은 상당히 비싼 작업이므로 이를 좀더 효율적인 iteration 버전으로 바꿀 수 있다. 실제로 방법 3은 a, b 가 매우 큰 서로소일 경우 답을 얻는데 꽤 오랜 시간이 걸리게 된다.
int gcd(int a, int b) { int tmp; while( b ) { tmp = a; a = b; b = tmp%b; } return a; } int main() { int a, b, g; cin >> a >> b; g = gcd(a,b); cout << "gcd = " << g << endl; cout << "lcm = " << (a*b)/g << endl; return 0; }


방법 5) Euclid's algorithm - Using Iteration, Original Version
유클리드가 처음 이 알고리즘을 제안했을때 사실은 modular 연산을 사용하지 않고, 아래와 같이 뺄셈 연산을 이용했다 한다.
int gcd(int a, int b) { if( a == 0 ) return b; while( b ) { if( a > b ) a = a-b; else b = b-a; } return a; } int main() { int a, b, g; cin >> a >> b; g = gcd(a,b); cout << "gcd = " << g << endl; cout << "lcm = " << (a*b)/g << endl; return 0; }  
방법5 는 방법 4와 비교하여, tmp 변수를 사용하지 않아도 되므로 메모리를 약간 절약한다는 장점이 잇다 ^^

유클리드 알고리즘의 증명 = 자세한 설명은 생략한다 Wikipedia 참고
유클리드 알고리즘의 시간복잡도 = O(n^2), n = length of integer bits, 그 이유는 n-bit 숫자 나눗셈 연산의 시간복잡도가 O(n(m+1)) 이기 때문이다 ( m 은 몫의 길이 )

3개 이상의 수에 대해 최소공배수와 최대공약수를 구할 때는, 두 수의 최소공배수와 최대공약수를 구한 후, 이 수와 나머지 수들에 대해 최소공배수와 최대공약수를 구하면 된다.

유클리드 알고리즘을 처음 보았을 때 무릎을 쳤던 기억이 난다. 그래서 최대공약수와 최소공배수에 대해서 글을 반드시 함 써보려 했는데... 위키피디아에 유클리드 알고리즘이 깔끔하고 멋지게 정리가 되어 있었다 ㅋ