[C++] 백준 2609번 최대공약수와 최소공배수

최대공약수와 최소공배수를 구하는 문제입니다.

소인수를 전부 구해서 배열에 넣습니다.
arr[x][y]에서 x는 소인수를 의미하고 y는 두개의 자연수를 의미합니다.

최대공약수

maxResult *= min(pow(i, arr[i][0]), pow(i, arr[i][1]));

최소공배수

minResult *= max(pow(i, arr[i][0]), pow(i, arr[i][1]));

 

 

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

int main(int argc, char *argv[])
{
	int x, y;
	int bigNum;
	int maxResult = 1;
	int minResult = 1;
	int arr[10010][2];

	cin >> x;
	cin >> y;

	bigNum = max(x, y);
	memset(arr, 0, sizeof(arr));

	while (1) {
		if (x == 1 && y == 1) {
			break;
		}

		for (int i = 2; i < bigNum; ++i) {
			if (x != 1 && x % i == 0) {
				++arr[i][0];
				x /= i;
				break;
			}
			if (y != 1 && y % i == 0) {
				++arr[i][1];
				y /= i;
				break;
			}
		}
	}

	for (int i = 2; i < bigNum; ++i) {
		if (arr[i][0] != 0 && arr[i][1] != 0) {
			maxResult *= min(pow(i, arr[i][0]), pow(i, arr[i][1]));
		}
		if (arr[i][0] != 0 || arr[i][1] != 0) {
			minResult *= max(pow(i, arr[i][0]), pow(i, arr[i][1]));
		}
	}

	cout << maxResult << endl;
	cout << minResult << endl;

	return 0;
}