백준 - 11653번

소인수분해

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

11653번: 소인수분해

시간초과한 경우

N = int(input())
numbers = [i for i in range(2, int(N/2)+1)]
i = 2
prime = []
while i*i <= numbers[-1]:
    if i in numbers:
        prime.append(i)
        numbers.remove(i)
    for num in numbers:
        if num % i == 0:
            numbers.remove(num)
    i += 1
prime.extend(numbers)
result = []
for num in prime:
    while N % num == 0:
        result.append(num)
        N = N // num
if result:
    for num in result:
        print(num)
else:
    print(N)

나누는 횟수를 줄이려고 N까지의 소수를 먼저 구한 뒤, 그 소수들로 나누는 작업을 했다. 그런데 이렇게 하니까 오히려 사용하지 않을 소수를 찾기 위해 많은 계산을 한 것 같다.

 

통과한 코드

import math
N = int(input())
for i in range(1, int(math.sqrt(N))):
    i += 1
    while N % i == 0:
        N /= i
        print(i)
if N != 1:
    print(int(N))

오히려 더 간단하게 N의 제곱근까지 나눠주고, 나눠지지 않는 수가 있다면 마지막에 화면에 출력해주는 것이 더 빨랐다.