백준 20946, 합성인수분해

개요

문제 링크
골드 5, 정수론, 소수판정
자연수를 합성수의 곱으로 분해하기

---

접근

1. 정수론은 실생활에는 큰 도움이 안되지만 코드포스에서 자주 다루는 주제이다. 이외에는 딱히 코테같은 곳에도 잘 안나온다.
2. 합성수로 인수분해를 한다. 우선 2개의 소수를 짝을 지어줘야 한다. 그러니 만약 N이 소수라면 당연히 합성수 분해를 할 수 없다. 왜냐? 2개의 소수가 없기 때문. 사전순으로 우선하려면? 가장 작은 2개의 소수끼리 짝을 지어야 한다.
3. 그런데 만약 소인수 분해 결과 소수의 개수가 홀수개라면? 즉 2개씩 짝을 지어서 하나가 남으면? 마지막에만 3개를 곱해주면 된다. 가장 먼저 출력될 놈이 가장 작아야 하니까 마지막에 큰 값을 출력할수록 이득이다. 이 부분에서 그리디를 끼운 것 같은데 그리디... 라고 하기에는 너무 단순하다.
4. 소인수분해의 정석은 N보다 작은 수에 대해 N과 나누어 떨어지면 vector에 추가하는 것이다. 그런데 N이 10^12이니까 소수에 대해서만 해줘야 한다. 그래서 에라토스테네스의 체가 필요하다. 범위는? 10^6까지 인데 왜냐하면 그 이상의 소수는 인수가 된다면 개수가 하나이다. 두 번 이상 곱해지면 N을 넘어가버려서 의미가 없다.
   즉, 2번 이상 곱할 수 있는 소수에 대해서만 체를 돌려주면 된다.
5. 소인수 분해를 빠르게 하려면 체를 따로 만들기보다, 체를 만들면서 소수가 발견되면 나눠주는 것이 좋다.

---

Pseudo code

P = 10^6
for (i = 2~P)
    if (!eras[i])
        while (n%i == 0)
            n/=i
            vector.push_back(i)
        for (j = i*i ~ P) // j += i
            eras[j] = 1
// 10^6보다 큰 소수
if (1 < n)
    vector.push_back(n)

// n = 소수
if (vector.size() == 1)
    return -1
while (vector.size())
    if (vector.size() == 3)
        cout << pop3()
    else
        cout << pop2()

---

Source code

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

#define P 1000000
using ld = long long;
int t[P];
typedef vector<ld> vec;

ld pop(vec &p) {
    ld v = p.back();
    p.pop_back();
    return v;
}

int main() {
    ld n;
    cin >> n;
    vec p;
    for (ld i=2; i<P; i++)
        if (!t[i]) {
            while (n%i==0)
                n/=i, p.push_back(i);
            for (ld j=i*i; j<P; j+=i)
                t[j] = 1;
        }
    if (1<n) p.push_back(n);
    reverse(p.begin(),p.end());

    if (p.size()==1)
        cout << -1;
    else {
        ld x, y;
        while (p.size()) {
            x = pop(p);
            y = pop(p);
            if (p.size() == 1)
                cout << x*y*pop(p);
            else
                cout << x*y;
            cout << " ";
        }
    }
}