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

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

 

소인수 분해는 $O(\sqrt N)$의 시간 복잡도로 $\sqrt N$까지 반복문을 돌아 자연수를 나누는 방법이 가장 잘 알려져 있다.

 

하지만 이 문제는 소인수 분해를 해야 할 수의 개수가 $N \leq 10^{6}$이므로 이 방법을 사용하면 TLE 판정을 받게 된다.

 

Linear sieve를 이용하여 소인수 분해를 $O(\log N)$에 할 수 있는 방법이 있다.

 

Linear sieve를 사용하여 소수 목록을 $O(N)$에 구한 후 소인수 분해를 실시하면 1초 이하의 시간으로 AC를 받을 수 있다.

 

Linear sieve를 알지 못한다면 이 글을 참조하여 사용하면 된다.