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

1.문제설명

에라토스테네스의 체를 이용하여 소인수분해를 해야하는 문제이다.

빠른 소인수분해를 위해 에라토스테네스의 체를 이용해서

단순히 소수를 판별하는 것을 넘어서

Prime[x] = y , x의 소인수 중 가장 작은 소수 y값을 저장하면

이를 바탕으로 소인수분해를 빠르게 할 수 있다.

예를 들어 10을 소인수 분해 할 때

Prime 배열은 다음과 같다

int x = 10 이라고 하면

Prime[x] == 2 이므로

2를 출력하고 x = x/2를 해준다

그러면 Prime[x] =5 이므로

5를 출력하고 x = x/5

x==1 이므로 종료한다.

이런식으로 에라토스테네스체를 이용하여 빠른 소인수분해를 할 수 있다.

2.문제풀이코드

#include <bits/stdc++.h>
using namespace std;
#define LEN 5000001


//Fast Factorization

int Prime[LEN];

//O(nloglogn)
void erathostenes(){
    Prime[0] = Prime[1] = -1;

    for(int i=2; i<LEN; i++){
        Prime[i] = i;
    }
    int sqrtn = int(sqrt(LEN));

    for(int i=2; i<=sqrtn; i++){
        for(int j=i*i; j<LEN; j+=i){
            if(Prime[j] == j){
                Prime[j] = i;
            }
        }
    }
}

//아마도 O(n) 이하
void Factorization(int num){

    while(num > 1){
        cout << Prime[num] << ' ';
        num /= Prime[num];
    }

    cout << '\n';
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0);

    int t;
    cin >> t;

    erathostenes();

    for(int T=0;T<t; T++){
        int num;
        cin >> num;
        Factorization(num);
    }


    return 0;
}