Python 소인수분해

아카이빙

import math
import sys

n = int(sys.stdin.readline().rstrip())
d = 2
sqrt = int(math.sqrt(n))

while d <= sqrt:
    if n % d != 0:
        d += 1
    else:
        print(d)
        n //= d

if n > 1: print(n)

아이디어 자체는 에라토스테네스의 체로부터 기인했다고 한다.

참고 문제