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

< 에라토스테네스의 체를 이용한 빠른 소인수분해 >

에라토스테네스의 체(The Sieve of Eratosthenes)를 아직 모른다면 저의 이전 포스팅을 참고하시기 바랍니다.

(http://plzrun.tistory.com/entry/폐구간1n-소수-구하기-에라토스테네스의-체-The-Sieve-of-Eratosthenes)

[1,N]값에 대해 소수인지 판별하는 방법인 '에라토스테네스의 체'를 이용하면,

[1,N]값에 대해 소인수분해를 빠르게 할 수 있다.

방법은 매우 간단하다.

1부터 N까지 가장 작은 인수(factor)를 에라토스테네스의 체를 이용하여 구하는 것이다.

이 값을 minFactor라 하자. (어떤 값 x의 minFactor는 minFactor[x]로 나타낸다.)

그러면 임의의 x값을 소인수 분해하기 위해서는 x가 minFactor[x]와 같을 때까지 x/=minFactor[x]를 반복하면 된다.

코드로 구현하면 다음과 같다.

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
    int minFactor[1000001];
    for(int i=0; i<1000001; i++) {
        minFactor[i]=i;
    }
 
    minFactor[0]=minFactor[1]=-1;
    for(long long i=2LL; i*i<=1000000; i++) {
        if(minFactor[i]!=i) continue; //소수가 아닌 경우
        for(long long j=i*i; j<=1000000; j+=i) {
            minFactor[j]=i;
        }
    }
 
    int n;
    scanf("%d", &n);
    vector<int> ret;
    //n을 소인수 분해 하면
    while(n!=1) {
        if(n%minFactor[n] == 0) ret.push_back(minFactor[n]);
        n/=minFactor[n];
    }
    sort(ret.begin(), ret.end());
    for(auto &p : ret) {
        printf("%d ", p);
    }
    puts("");
    return 0;
}

끝.