BOJ 1165 : 소인수 분해

문제

정수 N이 주어졌을 때, 소인수분해하는 프로그램을 작성하시오.

풀이

소인수 분해는 가장 작은 나눠지는 인수들로 분해하는 것인데, 나는 컴퓨터 속도를 믿고,, 시간복잡도가 O^2 인 계산을 때려버렸다. 그 이유는 중간에 break 문이 있기 때문에 간헐적으로 큰 값이 아니면 충분히 커버가 가능할 것이라 생각했기 때문

그래서 해답은 2부터 주어진 수인 10000000까지 차례로 나누다가 나누어 떨어지는 수가 있으면 추가하고 break를 건다, 그리고 해당 값으로 N을 나눴을 때 1이하로 떨어지면 처음의 while을 멈춘다.

import sys

if __name__ == '__main__':
    n = int(sys.stdin.readline())
    
    soinsu_list = []
    while n > 1:
        for i in range(2, 10000000):
            if n % i == 0:
                n /= i
                soinsu_list.append(i)
                break
            else:
                continue

    for d in soinsu_list:
        print(d)