소인수분해 문제

소인수분해가 필요한 문제는 크게 두 가지 방법으로 풀 수 있다.

1. 소인수분해를 시행하는 횟수가 시간에 큰 영향을 주지 않을 때

i를 2부터 루트n 까지 돌면서 n의 소인수에 해당한다면 추가하고 n을 i로 나눠주면 된다. 다 끝난 뒤에 n값이 1이 아닌지만 체크해주면 된다.

#include <stdio.h>
#include<map>
#include <math.h>
typedef long long ll;
using namespace std;
map<ll,ll> mp;
int main(){
    ll n;    scanf("%lld", &n);
    for(ll i=2 ; i*i<=n ; i++){
        while(n%i==0){
            mp[i]++;
            n/=i;
        }
    }
    if(n>1) mp[n]++;
     for(auto &here:mp)
        printf("%lld %lld\n",here.first,here.second);
 return 0;
}
 

시행 한 번당 시간복잡도는 O(sqrt(n))이다. 이 소인수분해 알고리즘은 단발성이므로 n의 개수가 많아질수록 시간은 커진다.

2. 소인수분해의 시행 횟수가 시간에 영향을 끼칠 때 (여러번 시행할 때)

만약 소인수분해를 여러번 해야 하는 상황이라면 1번의 방법에서 시간이 초과될 수 있다. 이럴 때는 지금의 설명할 방법을 사용해야 한다. 원리는 '에라토스테네스의 체' 알고리즘을 차용한다. 기존의 에라토스테네스 체 알고리즘은 i*j 숫자를 돌면서 소수가 아닌 수를 지워나가는 원리인데, 지금은 소수가 아닌 수를 찾았을 때 그 수의 가장 작은 인수를 저장해놓을 것이다. 저장해놓는 장소는 minfac[]이라는 배열이다. 따라서 우리는 n을 소인수분해할 때, 그 수를 어떤 수로 나눠야하는지 O(1)만에 알 수 있는 것이다. 이 방법은 전처리를 먼저 해놓은 다음에 소인수분해를 시행하기 때문에 초반에 전처리에 따른 시간cost는 들지만, 소인수분해를 여러번 시행할수록 유리해진다. 아래는 [BOJ 16563] 어려운 소인수분해 문제의 소스코드이다. 이 문제는 총 n개의 숫자들을 소인수분해 해야하는데, n이 100만으로 매우 크다. 따라서 단순히 1번에서 설명한 방식대로 n번 돌리면 시간이 터지게 된다.

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<iostream>
#include<functional>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stdlib.h>
#include<stack>
using namespace std;
const int SIZE=5000009;
int minfac[SIZE]={0};
int main(){
    int n;  scanf("%d",&n);
    minfac[0]=minfac[1]=-1;
    for(int i=2 ; i<SIZE ; i++)
        minfac[i]=i;
    for(int i=2 ; i*i<SIZE ; i++){
        for(int j=i*i ; j<SIZE ; j+=i){
            if(minfac[j]==j)
                minfac[j]=i;
        }
    }
    while(n--){
        int inp;    scanf("%d",&inp);
        vector<int> ans;
        while(inp>1){
            ans.push_back(minfac[inp]);
            inp/=minfac[inp];
        }
        sort(ans.begin(),ans.end());
        for(int here: ans) printf("%d ",here);
        printf("\n");
    }
    return 0;
}

이 방법의 시간복잡도는 일단 전처리과정에서의 '에라토스테네스의 체' 가 O(n * log(log n))이 소모된다. 그리고 소인수분해를 한번 시행할 때마다 O(log N)이 소모된다. 2의 인수로 아무리 많이 나와봐야 40개 안팎이다. 사실상 전처리 과정에서의 시간이 대부분이다. 시행횟수가 K번이라면 O(K*n*log(log n))이 될 것이다 (여기서 기술된 n은 위의 코드에서 사용된 변수 n이 아닌 inp로 간주해야 한다).