백준 20946 합성인수분해 (C++)

20946번: 합성인수분해

소인수분해 관련 문제이다. 문제에서는 합성인수분해가 여러개일 경우 사전 순으로 가장 앞서는 것을 출력하다고 되어있다. 그래서 먼저 소인수분해를 구한 후 이를 P(0)*P(1), P(2)*P(3) ... 과 같은 방식으로 출력해주었다. 만약 크기가 홀수인 경우 마지막 3개의 소수를 곱해 출력해준다. 로직을 생각해내는 것 까지는 간단했다. 그런데 계속해서 실패가 나와 굉장히 골치가 아팠다... 알고보니 N의 최댓값이 10^12이어서int 범위를 초과해서 일어난 오류였다.... 범위를 long long으로 바꿔주니 해결되었다. 범위를 잘 확인하자

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

long long N;

void solution() {
    vector<long long> v;
    vector<long long> answer;

    for (int i = 2; i <= sqrt(N); i++) {
        while (N % i == 0) {
            N /= i;
            v.push_back(i);
        }
    }
    if (N != 1) {
        v.push_back(N);
    }

    if (v.size() == 1) {
        cout << -1;
        return;
    }

    for (int i = 0; i < v.size(); i += 2) {
        if (i == v.size() - 1) {
            answer[answer.size() - 1] *= v[i];
        }
        else {
            answer.push_back(v[i] * v[i + 1]);
        }
    }

    for (auto elem : answer) {
        cout << elem << " ";
    }

}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> N;

    solution();

    return 0;
}