[백준] 2609번: 최대공약수와 최소공배수 C++로 풀어보기

2609번 설명

어떻게 풀까? (문제를 풀고 처음 든 생각)

최대공약수와 최소공배수라는 단어를 진짜 오랜만에 듣는다. 어떻게 구하는지도 기억이 가물가물하다.

소인수분해를 해서 나온 소인수들을 벡터에 저장하고, 최대공약수는 벡터에 저장해놓은 소인수들을 곱한 값으로,

최대공배수는 최대공약수에 소인수들로 나눠진 두 수를 곱해서 구하면 될 것 같다.

 

코드

#include <bits/stdc++.h>
using namespace std;


int main() {
	int a, b;
	vector <int> v;
	int max, min;
	int cnt = 1;
	
	cin >> a >> b;

	int x = 2;

	while (1) {

		if (a % x == 0 && b % x == 0) { // 공약수를 찾았으면
			a = a / x;
			b = b / x;
			v.push_back(x);
			x = 2;
		}
		else {
			x++;
		}

		if (x > a && x > b) {
			break;
		}
	}
		

	for (auto it = v.begin(); it != v.end(); it++) {
		cnt = cnt * (*(it));
	}

	min = cnt;
	max = cnt * a * b;

	cout << min << '\n';
	cout << max;

		
}

 

결과

2609번 결과

 

후기

학창시절의 추억이 떠오르던 문제였다. 코드를 보면 x가 a와 b보다 크면 break를 걸었는데, 다른 조건으로도 break를 걸 수 있을 것 같다는 생각이 들었다.