[C++] 유클리드 호제법 - 최대공약수(GCD)와 최소공배수(LCM)

유클리드 호제법 : 최대공약수(GCD)를 구하는 방법 중 하나!

최대공약수를 구하는 방법을 생각해보자.

0. 일반적인 접근법

---

N의 약수의 개수를 구하는 방법

1) 1부터 N 이하 정수로 N 을 나눠서 나머지가 0이 되는 수의 개수를 찾음

=> 시간 복잡도 O(N)

 

2) 1부터  √N 이하의 정수로 N 을 나눠서 나머지가 0이 되는 수의 개수를 찾고, 그 개수에 2를 곱한다.

=> 시간 복잡도 O( √N)

 

1. 유클리드 호제법

---

호제법 : 서로 나눈다는 것.

두 자연수 a, b 에 대해 (a > b) a를 b로 나눈 나머지를 r이라 하면,

a와 b의 최대공약수는 b와 r의 최대공약수와 동일.

 

b를 r로 나눈 나머지 r'을 구하고, 다시 r을 r'로 나눈 나머지를 구하는

과정을 반복해 나머지가 0이 되었을 때 나누는 수와 a와 b의 최대공약수.

 

ex) 1071과 1029의 최대공약수 구하기. GCD

1071은 1029로 나눠떨어지지 않으니 1071을 1029로 나눈 나머지 계산 => 42

 

1029는 42로 나눠떨어지지 않으니 1029를 42로 나눈 나머지 계산 => 21.

42는 21로 나눠떨어지니 1071과 1029의 최대공약수는 21.

 

public static int GCD(int a, int b){
	while(b != 0)
	{
		int temp = b;
		b = a % b;
		a = temp;
	}

	return a;
}

 

2. 최소공배수 LCM

---

이번엔 두 수의 최소공배수를 구하는 방법을 보자.

 

LCM(a, b) = a * b / GCD(a, b)가 성립.

 

어떤 두 수의 곱은, 그 두 수의 최대공배수와 최소공배수의 곱과 같다.

 

A와 B의 최대공약수를 G라 하자.

A = G * Q

B = G * K

 

=> 이 경우, A와 B의 최소공배수는 G * Q * K

 

public static int LCM(int a, int b){
	int gcd = GCD(a, b);
	return (a*b) / gcd;
}

 

3. 여담

---

gcd(a, b), lcm(a, b)

 

C++17에선 gcd, lcm 함수를 아예 라이브러리로 지원한다.

<numeric>  모듈을 가져다 쓰면 된다.

#include <numeric>

using namespace std;
int main()
{
	cout << gcd(18, 24) << endl; // 6
}