백준 BOJ 16563 - 어려운 소인수분해

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

16563번: 어려운 소인수분해

소인수분해를 빠르게 해주면 되는 문제.

"런타임 전의 전처리" 태그를 붙여줘도 나쁘지 않지 싶다.

소인수분해를 $k_i$를 입력받을때마다 직접 해주면 시간초과를 받기 쉽다.

소인수 분해를 위한 할수 있는 모든 준비를 미리 처리해둬서

최대한 빠르게 소인수분해를 해야 한다.

 

이를 위해서 수 k의 1이 아닌 약수 중 가장 작은 수를

미리 배열에다가 전처리해서 저장해줬다.

 

이렇게 하면 $k_i$를 입력받았을때 전처리한 배열 값을 참조,

그 수로 바로 출력하고 나눠서 최대한 빠르게 처리할 수 있다.

 

전처리를 위해서 에라토스테네스의 체를 응용했다.

어떠한 수 N에 대해서 N의 배수들을 순회하는데,

아직 배열값이 갱신되지 않은 수 M이 있다면

해당 수를 구성하는 1이 아닌 약수 중 가장 작은 수가 N이라는 말과 같으므로

arr[M] 을 N으로 갱신해주면 된다.

만일 M이 소수라면 자기자신으로 갱신해주면 된다.

 

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

int chk[5000001] = {0};

int main(){
	cin.sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	memset(chk, -1, sizeof(chk));
	chk[0] = 0;
	chk[1] = 1;
	for(int i=2; i<=5000000; i++){
		if(chk[i] != -1) continue;
		chk[i] = i;
		for(int j=i+i; j<=5000000; j+=i) if(chk[j] == -1) chk[j] = i;
	}
	
	int T,N;
	cin >> T;
	while(T--){
		cin >> N;
		while(N > 1){
			cout << chk[N] << " ";
			N /= chk[N];
		}
		cout << "\n";
	}
	return 0;
}

N이 1e6이므로 fastio를 사용해주도록 하자.