백준 16563번: 어려운 소인수분해 (C++)

https://www.acmicpc.net/problem/16563

16563번: 어려운 소인수분해

---

Solved By: Sieve of Eratosthenes

 

내 풀이 (시간 초과)

Sieve of Eratosthenes를 사용하여 MAX까지의 소수를 구한 다음, 주어진 N을 prime의 첫 값(2)부터 (n % prime[i] != 0)까지 나누고 나눈 소숫값을 결과에 저장하여 풀었습니다.

 

-> 시간 초과가 나온 이유를 어림짐작해보면 모든 소수를 탐색해서 그런가 싶습니다.

 

풀이

Sieve of Eratosthenes를 응용하여 MAX까지의 수까지 모든 수의 제일 작은 소인수를 구한 배열을 가집니다.

그럼 N이 주어지면 N의 소인수로 나누고, 그 소인수를 결과로 가지며 나눈 몫의 소인수를 또 나눕니다.

이 과정을 N이 1이 아닐 때까지 반복합니다.

 

+ 이 문제를 이해하기 위해서는 방문배열을 사용하지 않는 Sieve of Eratosthenes의 대한 지식이 필요합니다.

기존의 Sieve of Eratosthenes는 소수가 아닌 수를 0으로 저장한 배열을 가졌는데 이 문제에서는 0이 아닌 해당 수의 가장 작은 소인수를 할당하여 배열을 가지고, 이를 이용하여 문제를 풀었습니다.

 

이 방법이 시간 초과가 나지 않은 이유는 아마 필요한 소수들만 사용하여 문제를 풀었기 때문이라 생각합니다.

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#define MAX 5000001
using namespace std;

int T;
int minFactor[MAX];

void getFactor(){
    for(int i = 2; i < MAX; i++) minFactor[i] = i;
    for(int i = 2; i < MAX; i++){
        if(minFactor[i] == i){
            for(int j = i + i; j < MAX; j += i){
                minFactor[j] = i;
            }
        }
    }
}

vector<int> factorize(int n){
    vector<int> ret;
    while(n > 1){
        ret.push_back(minFactor[n]);
        n /= minFactor[n];
    }
    return ret;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> T;
    getFactor();
    while(T--){
        int n; cin >> n;
        auto res = factorize(n);
        sort(res.begin(), res.end());
        for(int i = 0; i < res.size(); i++){
            cout << res[i] << ' ';
        }
        cout << '\n';
    }
}