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)

import math

def solution(n):
    d = 2
    sqrt = int(math.sqrt(n))
    res = []
    while d <= sqrt:
        if n % d != 0:
            d += 1
        else:
            res.append(d)
            n //= d
    if n > 1:
        res.append(n)
    return res

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

참고 문제