유클리드 호제법

유클리드 호제법은 2개의 자연수의 최대공약수(GCD) 를 구하는 알고리즘이다.

a > b 인 두 자연수 a, b 에 대해서 a 를 b 로 나눈 나머지 a % b 를 r 이라고 했을 때, a, b 의 최대 공약수는 b, r 의 최대곡약수와 같다는 원리를 이용한 것이다.

위 과정을 계속 반복하여 r = 0 이 되었을때, 그 때의 나누는 수 b 가 a, b 의 최대공약수이다.

#include <iostream>

int GCD(int A, int B)
{
	int R = 0;
	while (0 != B)
	{
		R = A % B;
		A = B;
		B = R;
	}

	return A;
}

int main() 
{
	std::cout << GCD(48, 18);
	return 0;
}

6

최소공배수

2개의 자연수의 최소공배수(LCM) 는 최대공약수를 이용해 구할 수 있다.

a > b 인 두 자연수 a, b 에 대해서 a, b 의 최소 공배수는 (a * b) / (a, b 의 최대공약수) 이다.

#include <iostream>

int GCD(int A, int B)
{
	int R = 0;
	while (0 != B)
	{
		R = A % B;
		A = B;
		B = R;
	}

	return A;
}

int LCM(int A, int B)
{
	return (A * B) / GCD(A, B);
}

int main() 
{
	std::cout << LCM(48, 18);
	return 0;
}

144

std::gcd, std::lcm

numeric 헤더의 std::gcd, std::lcm 를 이용해 두 정수의 최대공약수, 최소공배수를 구할 수 있다.

#include <iostream>
#include <numeric>

int main() 
{
	std::cout << "최대공약수 : " << std::gcd(48, 18) << std::endl;
	std::cout << "최대공배수 : " << std::lcm(48, 18) << std::endl;
	return 0;
}

최대공약수 : 6
최대공배수 : 144