BOJ 2609 최대공약수와 최소공배수

GCD

유클리드 호제법 사용(재귀함수)

a,b 두 수가 있을 때

b가 0이 될때까지 a를 b로 나눈다.

b가 0이되면 a를 return 하게 된다.

 

LCD 

최소공배수 = 최대공약수 * (a / 최대공약수) * (b/최대공약수)

#include <iostream>
using namespace std;

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

int lcm(int g, int a, int b)
{
	int l = g * (a / g) * (b / g);
	return l;
}

int main()
{
	int a, b;
	cin >> a >> b;
	cout << gcd(a, b) << lcm(gcd(a, b), a, b);


	return 0;
}