[백준 문제풀이 / 정수론 및 조합론] 2609. 최대공약수와 최소공배수

문제 내용

두 수를 입력받아 최대공약수와 최소공배수를 찾는 문제

 

풀이

최대공약수와 최소공배수에 대한 공식을 이용해 풀었...?

두 수를 각 각  a,b, 최대공약수를 G, 최소공배수를 L 이라 칭했을 때 아래와 같은 성질이 있다.

 

1. a × b = G × L 

두 수의 곱은 최대공약수와 최소공배수의 곱과 같다.

2. L =  ( a × b ) ÷ G 

즉 최소 공배수는 두 수의 곱에서 최대 공약수를 나눈 것 과 같다.

 

#include <iostream>
using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int a, b;

	cin >> a >> b;

	int G, L;

	int num = 1;
	int smaller = min(a, b);
	while (1)
	{
		if (num > smaller)
			break;

		if (a % num == 0 && b % num == 0)
			G = num;

		num++;
	}



	int la, lb;
	la = a / G;
	lb = b / G;

	L = la * lb * G;

	cout << G << "\n" << L;


}

 

시간은 작게 나왔지만 최대공약수를 구하는데 있어서 불필요한 반복을 많이 한다.

 

#include <iostream>

using namespace std;

int main()
{
	int n,m;
	cin >> n >>m;

	int a = n;
	int b = m;

	if(m > n)
	{
		a = m;
		b = n;
	}
	int temp = 0;

	while(b > 0)
	{
		temp = a % b;
		a = b;
		b = temp;
	}

	cout << a << endl;
	cout << n * m / a << endl;
	return 0;
}

 

와 같이 나머지 연산을 이용하면 더 쉽게 구할 수 있다.