C++ 2609 최대공약수 최소공배수

나름 나눗셈으로 열심히 풀어보았지만..

계속해서 틀려 결국 구글링을 했는데 세상사람들 나 빼고 다 유클리드 호제법으로 풀었더라

 

내 틀린풀이

#include <iostream>


using namespace std;
int main()
{
	int a, b;
	cin >> a;
	cin >> b;

	int small = 0;
	int big=0;
	if (a > b)
	{
		small = b;
		big = a;
	}
	else if (a < b)
	{
		small = a;
		big = b;
	}
	//최대공약수
	int max;
	for (int i = small; i > 0; i--)
	{
		if (a % i == 0 && b % i == 0)
		{
			max = i;
			break;
		}
	}
	//최소공배수
	int min;
	for (int i = big; i < 10000000000; i++)
	{
		if (i % a == 0 && i % b == 0)
		{
			min = i;
			break;
		}
	}
	cout << max << endl << min;


}

 

웬만한 숫자는 다 정답이 나오는데, 큰 숫자를 넣었을 때 최소공배수를 구하면서 제대로 계산이 안되는 듯 했다.

 

 

 

그래서

유클리드 호제법이란?

 

 

유클리드 호제법

두 수의 최대 공약수를 구하는 알고리즘으로

A와 B의 최대공약수를 (A,B)라고 하고 A/B의 나머지를 R이라고 했을 때,

(A,B)=(B,R)인 것으로

이 연산을 계속해서 반복했을 때

(111,72)=(72,39)=(39,33)=(33,6)=(6,3)=(3,0)=3 

마지막으로 나오는 B가 두 수의 최대공약수가 된다.

 

 

또한 최소공배수는

최소공배수 = A*B/최대공약수 를 이용해 구할 수 있다.

 

 

 

그럼 이 원리를 이용하여 아래와 같이 구할 수 있는데, 

(이 코드보다 이 다음 코드가 더 깔끔합니다)

#include <iostream>
using namespace std;

int main()
{
	int a, b;
	cin >> a;
	cin >> b;
	int max, min; //최대공약수, 최소공배수
	
    int x = a;
	int y = b;
	while (y != 0)
	{
		int r = x % y;
		x = y;
		y = r;
		max = x;
	}
	
	min = a * b / max;
	cout << max << endl << min;

}

 

 

이렇게 해도 정답처리는 되나,

이를 더 깔끔하게 함수처리 해줄 수 있다.

 

#include <iostream>


using namespace std;

int gcd(int a, int b)				//최대공약수
{
	int temp;
	while (b != 0)
	{
		temp = a % b;
		a = b;
		b = temp;
	}
	return a;
}
int lcm(int a, int b, int max)		//최소공배수
{
	return a * b / max;
}
int main()
{
	int a, b;
	cin >> a;
	cin >> b;

	cout << gcd(a, b) << endl << lcm(a, b, gcd(a, b)) << endl;

}