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

입력 수가 최대 백만 개이므로, 수 하나마다 처음부터 나눠 보는 방식은 부담이 크다. 먼저 체로 합성수를 표시하고, 각 수를 작은 소수부터 나누며 인수를 출력했다.

어떤 소수로 나누어지는 동안은 계속 나누고, 더는 나누어지지 않으면 다음 소수로 이동한다. 마지막에 남은 값이 1이 아니면 그것도 소수 인수다.

이 문제에서는 많은 질의 앞에서 전처리 비용을 먼저 내는 선택이 중요했다.

문제: 16563 어려운 소인수분해 · 코드: GitHub에서 보기