문제
지원이는 대회에 출제할 문제에 대해서 고민하다가 소인수분해 문제를 출제해야겠다고 마음을 먹었다. 그러나 그 이야기를 들은 동생의 반응은 지원이의 기분을 상하게 했다.
"소인수분해? 그거 너무 쉬운 거 아니야?"
지원이는 소인수분해의 어려움을 알려주고자 엄청난 자신감을 가진 동생에게 2와 500만 사이의 자연수 N개를 주고 소인수분해를 시켰다. 그러자 지원이의 동생은 기겁하며 쓰러졌다. 힘들어하는 지원이의 동생을 대신해서 여러분이 이것도 쉽다는 것을 보여주자!
입력
첫째 줄에는 자연수의 개수 N (1 ≤ N ≤ 1,000,000)이 주어진다.
둘째 줄에는 자연수 ki (2 ≤ ki ≤ 5,000,000, 1 ≤ i ≤ N)가 N개 주어진다.
출력
N줄에 걸쳐서 자연수 ki의 소인수들을 오름차순으로 출력하라.
풀이
소인수분해는 주어진 수를 소수로 분할하는 과정이다.
1 부터 ki까지 다 돌아가면서 소인수분해를 하는 과정은 시간초과가 나기 굉장히 쉽다.
그러므로 에라토스테네스의 체를 이용하여 소수를 미리 구해준 다음에, 소인수분해를 해주면 된다.
기본적으로 어떤 수를 N이라 하면, 인수의 절반은 N^1/2 이하가 되고, 이를 이용해서 미리 전체 소수를 구해주면 된다.
ki의 범위가 5000000이므로 5000000^1/2까지 구해주면 되는것이다.
그리고 에라토스테네스의 체를 이용해야 하는 이유는
기본적으로 1 ~ 5000000까지의 모든 수를 N^1/2까지 반복문을 돌며 소수를 판별해주면 5000000 5000000^1/2 = X 1000000000라는 수가 나오게 된다.
이러면 1초안에 구할 수 없기 때문에, 5000 * 5000 2차원 배열을 만들어 에라토스테네스의 체를 수행하는 이중 반복문을 만들어 주면 된다.
정답 코드
#include <iostream>
#include <vector>
#include <cmath>
#define MAXINT 5000000
using namespace std;
int N, c_prime[5001];
vector<int>prime;
int main(){
ios::sync_with_stdio(0);
cout.tie(0); cin.tie(0);
cin>>N;
for(int i=2; i<=5000; i++)
for(int j=1; j<=5000; j++){
if(i*j > 5000) break;
if(j == 1) c_prime[i] = max(c_prime[i], 0);
else c_prime[i*j] = 1;
}
for(int i=2; i<=sqrt(MAXINT); i++)
if(!c_prime[i]) prime.push_back(i);
for(int i=0; i<N; i++){
int c;
cin>>c;
for(auto p : prime){
while(c != 1 && c%p == 0 && c>=p){
cout<<p<<' ';
c = c/p;
}
}
if(c != 1)
cout<<c;
cout<<'\n';
}
}