[c++] 2702번 초6 수학

문제

 

 

코드

#include <iostream>
#include <cmath>
using namespace std;

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

int lcm(int a, int b)
{
	return a * b / gcd(a, b);
}

int main()
{
	int n;
	cin >> n;
	int x, y;
	for (int i = 0; i < n; i++)
	{
		cin >> x >> y;

		cout << lcm(x, y) << " " << gcd(x, y) << endl;
	}

	return 0;
}

 

알고리즘

 

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

바로 gcd를 구하는 코드를 알면 쉽게 풀 수 있지만 이에 대한 코드가 모르면 갈피를 잡지 못할 수 있습니다. 

 

유클리드 알고리즘이라고 불리는 이 것은 주어진 두 수 사이에 존재하는 최대 공약수를 구하는 알고리즘입니다.

 

작동 원리는 자연수 x, y가 주어질 때 큰 수가 x라고 하면 x를 y로 나눠 나머지가 0이 아니면 x와 y를 바꾼 후 나머지가 0일 때까지 반복하는 것입니다.

 

1, 'x'를 'y'로 나눈 나머지를 'r' 이라고 할 때, gcd(x, y)는 gcd(y, r)과 같습니다.

2. r이 0이 될 때, 'y'가 x와 y의 최대공약수입니다.

이 과정을 반복하여 r이 0이 될 때까지 나눗셈을 수행합니다.

 

최소공배수 공식(최대공약수를 이용)

• a,b: 최소공배수를 구하고자 하는 두 수
• gcd(a,b): a와b의 최대공약수
• (최소공배수 * 최대공약수 = a * b)를 이용
• 식: a * b / gcd(a,b)

최소공배수는 gcd(a,b)를 분모로, a*b를 분자로 놓어서 구하면 됩니다.