최대공약수 (유클리드호제법) 최소공배수

최대공약수란 ?

어떤 수 A 와 B가 있을 때 A 와 B 서로의 약수에서 공통된 수들 중 가장 큰 수를 의미한다.

가장 간단하게 구할 수 있는 방법은 A와 B중 작은 값을 구하여 2부터 작은 값 까지 순회하면서 A와 B의 나머지 연산을 통해 구하는 방법이 있다. 해당 방법은 시간복잡도 o(N) 이라는 시간복잡도를 가지고 있으며 해당 방법보다 빠른 유클리드 호제법이라는 알고리즘이 존재한다.

유클리드호제법의 로직은 다음과 같다.

int gcd(int a, int b){
	if (b == 0){
		return a;
	}
	else {
		return gcd(b, (a%b));
	}
}

int main(){
	int aNum, bNum;

	cin >> aNum;
	cin >> bNum;

	cout << gcd(aNum, bNum);
}

  위와 같이 제귀호출을 이용하여 구할 수 있다.

A = 24, B = 16

A의 자리에 B를 넣고 B의 자리에 A % B를 한 결과 값을 넣는다. A % B의 값이 0이 될 때 A의 값은 최대 공약수이다.

(24, 16) -> (16, (24 % 16)) -> (16, 8) -> (8, (16 % 8)) -> (8, 0) 

위와 같은 과정을 거쳐 16 % 8의 나머지는 0 이므로 A의 값인 8은 최대 공약수가 된다.

 

추가적으로 A * B의 값은 최대공약수와 최소공배수를 곱한 값과 같다. 따라서 최대공약수만 구한다면 (A * B) / 최대 공약수 를 한 값으로 최소공배수를 구할 수 있다.