[2609번] 최대 공약수와 최대 공배수

2609번: 최대공약수와 최소공배수

 

www.acmicpc.net

우리가 어린 시절 배웠던 두 수의 최대 공약수, 최소 공배수 구하는 방법은

각 수의 약수를 구해 공통된 약수들 중 가장 큰 수가 최대 공약수 였고,

각 수의 배수들 중 공통된 배수 중 가장 작은 수가 최소 공배수 였다.

그 때 당시 배웠던 방법을 토대로 코드를 작성해 보면 다음과 같다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int max_div, min_mult = 1;
int num1, num2, div_n = 2;
int input[2];//입력 받은 두 수
vector< vector<int> >div_num;

bool desc(int a, int b) {
	return a > b;
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> input[0] >> input[1];
	for (int i = 0; i < 2; i++) {
		vector<int>temp;
		for (int j = 1; j*j < input[i]; j++) {
			if (input[i] % j == 0) {
				temp.push_back(j);
				temp.push_back(input[i] / j);
			}
		}
		div_num.push_back(temp);
	}

	for (int i = 0; i < 2; i++) sort(div_num[i].begin(), div_num[i].end(), desc);//내림차순 정렬
	//최대 공약수
	for (int i = 0; i < div_num[0].size(); i++) {
		for (int j = 0; j < div_num[1].size(); j++) {
			if (div_num[0][i] == div_num[1][j]) { //비교 하다가 같은 수를 만나면 반복 종료
				max_div = div_num[0][i];
				break;
			}
		}
		if (max_div != 0)break;//최대 공약수를 구했으면 반복 종료
	}
	//최소 공배수
	num1 = input[0];
	num2 = input[1];
	while (1) {
		if (num1 % div_n == 0 && num2 % div_n == 0) {// 두 수가 동시에 나눠질 때
			min_mult *= div_n;
			num1 /= div_n;
			num2 /= div_n;
		}
		else {//나눠 지지 않을 때
			if (div_n < num1 || div_n < num2) div_n++; // 아직 나누는 수보다 남은 수들이 클때는 나누는 수를 증가시켜준다.
			else {//남은 수들이 같거나 작으면 남은 수들도 곱해준다.
				min_mult = min_mult * num1*num2;
				break;
			}
		}
	}
	cout << max_div << '\n' << min_mult;
}

 

상당히 비효율적이고 긴 코드가 나오는데 이 코드를 깔끔하고 쉽게 줄일 수 있다.

그 방법은 유클리드 호제법을 사용하는 것이다.

---

유클리드 호제법이란 2개의 자연수 또는 정식의 최대공약수를 구하는 알고리즘 중 하나로

2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면 (단, a>b),

a와 b의 최대공약수는 b와 r의 최대공약수와 같다.

이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여

나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다.

이는 명시적으로 기술된 가장 오래된 알고리즘으로서도 알려져 있으며, 기원전 300년경에 쓰인 유클리드의 《원론》 제7권, 명제 1부터 3까지에 해당한다.

출처 : https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95

---

쉽게 말해서 두 수 중 큰 수에 작은 수를 나눠 나머지가 0이 될 때 까지 몫과 나머지를 이용해서 나누는 것이다.

나머지가 0이 되면 그 식에서의 몫이 최대공약수가 된다.

최소 공배수는 두 수를 곱해서 최대 공약수를 나눠 주면 된다.

#include <iostream>
using namespace std;
int num1, num2, gcm;

int GCM(int n1, int n2) {
	if (n1%n2 == 0) return n2;
	else return GCM(n2, n1%n2);
}

int main(){
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> num1 >> num2;
	gcm = num1 > num2 ? GCM(num1, num2) : GCM(num2, num1);
	cout << gcm << '\n' << num1 * num2 / gcm;
}