Baekjoon(C++)
[백준] 2609번: 최대공약수와 최소공배수 C++로 풀어보기
어떻게 풀까? (문제를 풀고 처음 든 생각) 최대공약수와 최소공배수라는 단어를 진짜 오랜만에 듣는다. 어떻게 구하는지도 기억이 가물가물하다. 소인수분해를 해서 나온 소인수들을 벡터에 저장하고, 최대공약수는 벡터에 저장해놓은 소인수들을 곱한 값으로, 최대공배수는 최대공약수에 소인수들로 나눠진 두 수를 곱해서 구하면 될 것 같다. 코드 #include using namespace std; int main() { int a, b; vector 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); ..
