백준 20946 합성인수분해

 

#include <stdio.h>
#include<queue>
#include<iostream>
#include<stack>
#include<vector>
#include<set>
#include<algorithm>
using namespace std;
void fast_io() {
  cin.tie(0)->sync_with_stdio(0);
}
bool chk[1000001];
vector<long long> solve;
int main(){
    fast_io();
    long long N;
    cin>>N;
    chk[1]=true;
    priority_queue<long long,vector<long long>,greater<long long>> pq;
    for(long long x=2;x*x<=N;x++){
        if(chk[x]) continue;
        for(long long y=x*2LL;y*y<=N;y+=x){
            chk[y]=true;
        }
    }
    long long now=N;
    for(long long x=2;x*x<=N;x++){
        while(now%x==0){
            pq.push(x);
            now/=x;
        }
    }
    if(now!=1) pq.push(now);
    while(!pq.empty()){
        if(pq.size()>3){
            long long a=pq.top();
            pq.pop();
            long long b=pq.top();
            pq.pop();
            solve.push_back(a*b);
        }
        else if(pq.size()==3){
            long long a=pq.top();
            pq.pop();
            long long b=pq.top();
            pq.pop();
            long long c=pq.top();
            pq.pop();
            solve.push_back(a*b*c);
        }
        else if(pq.size()==2){
            long long a=pq.top();
            pq.pop();
            long long b=pq.top();
            pq.pop();
            solve.push_back(a*b);
        }
        else{
            cout<<-1;
            return 0;
        }
    }
    for(auto i : solve){
        cout<<i<<" ";
    }
}

http://www.acmicpc.net/problem/20946 

20946번: 합성인수분해

소수의 성질을 이용해 푸는 문제였습니다.

N의 범위가 10^12까지이므로 우리는 소수의 성질인 어떤 수의 제곱근까지의 소인수를 알아내면 모든 소인수를 알아낼수 있는 성질을 이용하면됩니다. O(10^6)가 되므로 시간안에 풀수 있습니다. N의 소인수들을 오름차순으로 정렬하고 2개씩 끊고 마지막에 3개가 남게되면 3개씩 끊어 마무리하면 됩니다.