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개 이상의 수에 대해 최소공배수와 최대공약수를 구할 때는, 두 수의 최소공배수와 최대공약수를 구한 후, 이 수와 나머지 수들에 대해 최소공배수와 최대공약수를 구하면 된다.

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

크리에이티브 커먼즈 라이선스

이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리 2.0 대한민국 라이선스에 따라 이용하실 수 있습니다.

어떤 자연수 n 이 소수인지 구할때, n 이 작을 경우에는 다음과 같은 방법을 사용한다.

1. Trial Division
소수의 성질을 이용, 어떤 수 n 이 소수인지 판별하기 위해 n 을 2 부터 n-1 까지 하나씩 나누어보아 나누어 떨어지는 수가 존재하지 않으면 n 은 소수가 된다.

Notes
- 2를 제외한 모든 소수는 홀수이므로, 어떤 수 n 이 짝수이면 소수가 아니다.
- 만약 N 이 합성수라면 N = a*b 형태가 되므로 ( a > 1 && b > 1 ), a 와 b 둘 중 하나는 sqrt(N) 보다 작거나 같음을 알 수 있다. 그러므로 N 을 2부터 sqrt(N) 까지 나눠보아 나누어지지 않으면 N 은 소수가 된다.

2. 에라토스테네스의 체(Sieve of Eratosthenes)
n 이 작을 때 ( 일반적으로 n <= 10,000,000 ) 2 부터 n 까지의 소수를 찾는 가장 효율적인 방법으로 알려져 있다. 어떤 수 P 가 소수이면 P 로 나눌 수 있는 P 의 배수들은 소수가 아닌 것으로 체크한다. 이러한 과정을 반복하면서 주어진 [2,n] 구간 내에서 소수를 찾아낸다.

소수일 것 같은 수 (Probable Prime) 판별법
어떤 자연수 n 이 소수인지 아닌지 판별할 때, n 이 매우 커지면 유한시간내에 n 이 소수인지 판별하기 곤란해지게 된다. 이 때문에 n 의 소수 여부를 판별하는 근사해를 구하는 검사법이 여럿 개발되었는데, 이 검사법에 의해 n 이 합성수가 아님이 판별되는 경우에 n 을 소수일 것 같다 (Probable Prime) 고 한다.
Probable Prime (PRP) 의 정의는, 소수가 갖는 특정 상태를 만족하는 자연수이다.

1. Wheel Factorization
소수의 특징 중 하나인 [2,n] 구간내에 존재하는 소수의 갯수는 n 이 커질 수록 분포도가 희박해진다는 점에서 착안한 방법. 에라토스테네스의 체의 특수한 응용방법이다. 기본 원리는 에라토스테네스의 체와 동일하나, 구간내의 모든 소수에 대해 배수를 찾아 검사하는 것이 아니라 몇개의 소수를 가지고 이 수들로 나누어지는 수들을 걸러내는 방식으로 구하는 것이 차이점이다. 소수 2, 3을 가지고 Wheel Factorization 을 한다면, 우선 2와 3 의 배수를 모두 소수가 아닌 것으로 판별한다. 그리고 그 다음 소수인 5, 7 를 이용해 또다시 이 작업을 반복한다.
일반적으로 많이 쓰는 factorization 은 6N+1, 6N+5 를 사용하여 주어진 구간 [1,n] 내에서 나누어 지지 않는 수를 소수일 것 같은 수로 판별한다. ( Wheel Factorization 은 n 이 커질수록 정확도가 떨어지므로 이를 위해 n 이 커질수록 더 많은 소수를 이용해 나누어보아야 한다. )

 
for all

Probable Prime 판별법은 이외에도 여러가지가 개발되어 있다.


참고1
임의의 큰 자연수를 소인수분해하는 문제는 NP 문제로 알려져 있다.
거대한 합성수의 소인수분해는 암호문 해독에 응용되어, 기존의 암호문 전달 체계와 다른 암호학에 공공열쇠 개념을 도입하여 리베스트(Ron Rivest)와, 샤미르(Adi shamir), 아들만(Len Adleman)의 이름을 딴 RSA방식이라는 암호이론이 개발되기도 했다.
http://mathworld.wolfram.com/PrimalityTest.html


참고2 - 관련 사이트
TopCoder Tutorial : Primality Test - Non Deterministic Algorithms
Wikipedia

크리에이티브 커먼즈 라이선스

이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리 2.0 대한민국 라이선스에 따라 이용하실 수 있습니다.