[Algorithm] 최대공약수, 최소공배수 구하기

학교에서 배운 최대공약수와 최소공배수의 정의는 다음과 같습니다.

 

최대공약수(GCD, Greatest common divisor): 여러개의 정수중 그들 모두의 약수가 되는 공약수(Common divisor)중 최대값

최소공배수(LCM, Least common multiple): 여러 개의 정수중 그들 모두의 배수가 되는 공배수(Common multiple)중 최소값

 

우선, 최대공약수는 유클리드 호제법(Euclidean algorithm)을 사용하여 구할 수 있습니다.

유클리드 호제법은 2개의 자연수의 최대공약수를 구하는 알고리즘입니다. 유클리드 호제법의 정확한 설명은 다음과 같습니다.

 

A를 B로 나눈 나머지 값을 R이라고 할 때, A와 B의 최대공약수는 B와 R의 최대공약수와 같다

 

예를 들어서 62와 24의 최대공약수를 유클리드 호제법으로 구해보겠습니다.

 

62%24=14

24%14=10

14%10=4

10%4=2

4%2=0

 

R이 0이될때, B값의 자리에 있는 2가 62와 24의 최대공약수가 됩니다.

 

그리고 최소공배수는, A와 B의 곱이 최소공배수와 최대공약수의 곱이라는 것을 사용해주면 구할 수 있습니다.

 

다음을 C++로 구현해 보겠습니다.

#include <iostream>
#include <algorithm>  
using namespace std;
int gcd(int a, int b) {
	if (a < b)
		swap(a, b);
	while (true) {		
		if (a%b == 0) {
			return b;
		}
		else {
			int tmp = a;
			a = b;
			b = tmp%b;
		}
	}
}
int lcd(int a, int b) {
	return a * b / gcd(a, b);
}

gcd()는 반복문 뿐만아니라 재귀적인 방식으로도 구현할 수 있습니다. 재귀적인 방법으로 구현하게 된다면, 코드는 반복문으로 구현한 gcd()함수보다 훨씬 간결해지지만, 메모리를 더 차지한다는 단점이 있습니다. 하지만 gcd()함수 특성상, 재귀 깊이가 매우 커질 수 없기 때문에 재귀적인 방식으로도 구현해도 크게 상관없습니다.

 

한번 직접 도전해보세요.