[C++] GCD (Greatest Common Divisor) 최대 공약수

https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95

유클리드 호제법 - 위키백과, 우리 모두의 백과사전

 

유클리드 호제법으로도 불립니다.

GCD는 굉장히 간단한 코드라서 외워서 쓸 정도인데 막상 안보고 구현하려니 헷갈려서

유도 방식을 직접 써서 생각해보게 되었습니다.

 

GCD (21, 12)     (참고로 GCD(12, 21)을 해도 12 % 21 = 12로 21 % 12로 바뀜)

21	%	12	=	9
		12	%	9	=	3
				9	%	3	=	0

GCD (21, 12) = 3

 

위의 숫자들을 그대로 가져와서 써주면 됩니다.

#include <iostream>

using namespace std;

int GCD(int a, int b)
{
	while (b != 0)
	{
		int c = a % b;
		a = b;
		b = c;
	}

	return a;
}

int main()
{
	cout << GCD(21, 12);
}

 

추가적으로 a와 b의 최대 공배수를 구하는 방법은

a * b / GCD(a, b) 로 할 수 있습니다.

 

ex)

8 과 10의 최소 공배수 구하기

8 * 10 / GCD(8, 10)   ( GCD(8, 10) = 2 )

8 * 10 / 2 = 40