2.2.4 Prime Factorization

개념

$2$ 이상의 자연수를 소수들의 곱으로 나타내는 과정입니다. 예를 들어 $60=2\times2\times3\times5=2^2\times3\times5$입니다. 어떤 소수가 몇 번 곱해져 있는지 알면 약수의 개수를 세거나 여러 수의 공통 인수를 찾을 수 있습니다.

작은 인수부터 나누기

$2$부터 차례대로 나누어떨어지는지 확인합니다. 나누어떨어지면 그 인수를 기록하고 몫에 대해 같은 인수로 다시 나눕니다. 같은 소수가 여러 번 곱해져 있을 수 있기 때문입니다.

앞에서 작은 소인수를 모두 나누었으므로, 뒤에서 새로 발견하는 인수는 소수입니다. 예를 들어 $4$로 나누어떨어지는 수라면 먼저 검사한 $2$로도 나누어떨어졌을 것이므로, $2$를 모두 제거한 뒤에는 $4$가 인수로 나올 수 없습니다.

제곱근까지만 확인하는 이유

현재 남은 값을 $R$이라고 하겠습니다. $R>1$이고 소수가 아니라면 $R=a\times b$처럼 $1$보다 큰 두 자연수의 곱으로 나눌 수 있습니다. 이때 두 수가 모두 $\sqrt R$보다 크면 곱이 $R$보다 커집니다. 따라서 두 인수 중 적어도 하나는 $\sqrt R$ 이하입니다.

예를 들어 $36$을 $1$보다 큰 두 자연수로 나눈 인수 쌍은 $(2,18)$, $(3,12)$, $(4,9)$, $(6,6)$입니다. 각 쌍의 작은 쪽이 모두 $\sqrt{36}=6$ 이하이므로 $6$까지 확인하면 인수를 찾을 수 있습니다. 같은 이유로 검사할 수를 $d$라고 하면 $d^2\le R$인 동안 확인하면 됩니다. 등호는 $49=7\times7$처럼 같은 인수 두 개의 곱도 확인하기 위해 필요합니다.

나누기를 할 때마다 $R$이 줄어드므로 검사 범위도 함께 줄어듭니다. $60$을 $2$, $2$, $3$으로 나누면 $R=5$가 되고, $3^2>5$이므로 더 검사할 필요가 없습니다.

마지막에 남은 값

검사가 끝났을 때 $R>1$이면 그 값은 소수이므로 마지막 소인수로 기록합니다. 만약 합성수였다면 제곱근 이하의 소인수가 있어야 하는데, 그 범위의 인수는 앞에서 이미 모두 제거했기 때문입니다. 위 과정에서는 마지막으로 $5$를 기록해 $2,2,3,5$를 얻습니다. 남은 값이 $1$이면 모든 소인수를 이미 기록한 상태입니다.

입력이 처음부터 소수인 경우에는 나누기가 한 번도 일어나지 않습니다. 이때는 원래 수의 제곱근까지 검사한 뒤 그 수 자체를 소인수로 기록합니다.

복잡도

분해할 자연수를 $N$이라고 합니다. 찾은 인수를 바로 출력하면 추가 공간은 $O(1)$이고, 결과를 모아 저장하면 $O(\log N)$입니다.

예제

문제

양의 정수를 소인수분해하여 소인수를 작은 순서대로 출력하여라.

입력

첫째 줄에 양의 정수 $N$이 주어진다. $2\le N\le9\,999$이다.

출력

소인수를 공백으로 구분하여 출력한다. 같은 소인수가 여러 번 사용되면 모두 출력한다.