Problem
https://www.acmicpc.net/problem/11653
Solution
code1
1
2
3
4
5
6
7
8
9
10
11
import sys
n = int(sys.stdin.readline())
last_insu = 2
while n>1:
for i in range(last_insu,n+1):
if n % i == 0:
sys.stdout.write(str(i) + '\n')
n //= i
last_insu = i
break
위 코드는 정석적으로 작은수부터 나눠나가면서 소인수분해를 하는 방법이다. 처음 작성했을 당시 큰 값이 입력되었을 때 시간초과가 나올 확률이 높아보여 아래의 방법을 사용하여 제출하였다.
code2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import sys
def prime_list(n):
sieve = [True] * n
m = int(n ** 0.5)
for i in range(2, m + 1):
if sieve[i] == True:
for j in range(i+i, n, i):
sieve[j] = False
return [i for i in range(2, n) if sieve[i] == True]
n = int(sys.stdin.readline())
insu_list = prime_list(n+1)
last_insu = 0
while n>1:
for i in range(last_insu, len(insu_list)):
if n % insu_list[i] == 0:
sys.stdout.write(str(insu_list[i]) + '\n')
n //= insu_list[i]
last_insu = i
break
위 코드는 에라토스테네스의 체를 활용하여 주어진 정수까지의 소수를 구한 뒤 그 안에서 인수를 찾아나가는 방식이다.
Memo
에라토스테네스의 체가 소수판별을 할 때 효율적이라는 사실만으로 아래의 방식을 먼저 사용하였는데 놀랍게도 채점결과는 정반대였다. 아래 결과를 보면 2번이 채점시간은 2배, 메모리는 무려 4배가 넘게 나왔다. 
원인을 찾아보니 2번은 체를 구하는 과정이 O(Nloglog N)만큼의 시간복잡도가 나오는데반해 1번은 소수를 찾는 과정이 O(sqrt(N))이기 때문에 더 빠른 것이라고 한다.