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

소인수분해의 시간복잡도는 N-bit의 수에 대해 아직 N에 대한 지수승입니다.(다만 소인수분해는 NP-complete는 아니고 NP-intermediate입니다.) N이 최대 10000000이기 때문에 정말 이상하게 짜지만 않으면 시간은 별 문제가 되지 않을 것입니다.

조금이나마 연산을 줄이기 위해 주어진 N을 p(2로 시작해서 1씩 증가함)로 계속 나누어보고, 나누어떨어지면 p를 출력하고 N에 N/p를 대입했습니다. N이 N/p로 줄어든 이후에는 다시 2부터 나누어보는 것이 아니라 p부터 시작했습니다.

https://github.com/encrypted-def/BOJ/blob/master/11653.cpp