소인수분해

import sys


def main():
    input = sys.stdin.readline

    n = int(input())

    i = 2
    while n != 1:
        while n % i == 0:
            print(i)
            n //= i
        i += 1


main()

소인수분해

$1$보다 큰 자연수를 소인수만의의 곱으로 나타낸 것을 소인수분해(prime factorization)라고 합니다. 다음은 소인수분해의 예시입니다.

• $42 = 2 \times 3 \times 7$
• $100 = 2 \times 2 \times 5 \times 5$
• $101 = 101$ (소수)

산술의 기본 정리에 따라 양의 정수의 소인수분해는 유일하게 존재합니다.

$n$의 소인수분해는 $n$이 $1$이 될 때까지 $2$(가장 작은 소수)부터 시작하여 $n$을 나누어 떨어지게 하는 수를 계속해서 나누어주면 됩니다. 코드에서 i가 합성수인 경우, 그 전에 i의 모든 소인수로 $n$을 나누어 주었기 때문에 바로 다음 i로 넘어가게 됩니다. 따라서 출력되는 i는 항상 소수이며, 작은 수부터 출력됨이 보장됩니다.