백준 - (# 11653)

https://www.acmicpc.net/problem/11653
정수 N이 주어졌을 때, 소인수분해하는 프로그램을 작성하시오.

Code

n = int(input())

while n > 1:
    prime_factor_candidates = [x for x in range(2,int(n**0.5)+1)]+[n]
    for i in prime_factor_candidates:
        if n % i == 0:
            print(i)
            n = n // i
            break

참고
제곱근을 구하기 위해 math.sqrt()를 사용했을 때보다 **0.5를 사용하는 것이 시간이 더 짧게 나왔다.

리먼 소인수분해로 $O(N^{\frac{1}{3}})$으로도 가능하다고 한다.
https://www.acmicpc.net/blog/view/89