[알고리즘] 소인수분해

n = int(input())

while n % 2 == 0: # 2로 나누어지면 n에 2를 나누고 2를 출력
    n //= 2
    print(2)
    
for i in range(3, int(n ** .5) + 1, 2): # 3부터 루트n까지 2씩 증가
    while n % i == 0: # i로 나누어지면 n에 i를 나누고 i를 출력
        n //= i
        print(i)
    if n == 1: break # n == 1 이면 for문 탈출
    
if n != 1:
    print(n) # 입력받은 n이 소수이면 아무런 계산도 하지 않고 그대로 나옴

 

#입력값
72

#출력값
2
2
2
3
3

# 입력값
9991

# 출력값
97
103