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

 

해결방법

최대공약수와 최소공배수를 구하는 공식을 알고 있다면 쉽게 구할수 있다.

 

두 수 a와 b를 가지고 문제를 푼다고 가정했을때

최대공약수의 경우 a를 b로 나눈 나머지 값이 0과 같다면 b가 최대공약수가 되고, 아니라면 b와 b를 a와 b로 나눈 나머지를 가지고 반복을 해주는 형태로 구할 수 있다.

 

최소공배수의 경우 a와 b의 곱을 최대공약수로 나눠준 값이 된다.

 

정답 코드

#include <iostream>

using namespace std;

int GCD(int a, int b)
{
	return (a % b == 0 ? b : GCD(b, a % b));
}

int LCM(int a, int b)
{
	return a * b / GCD(a, b);
}

int main()
{
	int A, B;
	cin >> A >> B;

	cout << GCD(A, B) << endl;
	cout << LCM(A, B) << endl;

	return 0;
}