11653 : 소인수분해

문제

정수 N이 주어졌을 때, 소인수분해하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다.

---

출력

N의 소인수분해 결과를 한 줄에 하나씩 오름차순으로 출력한다. N이 1인 경우 아무것도 출력하지 않는다.

---

예제

72
>>
2
2
2
3
3

---

풀이

from sys import stdin

N = int(input())

divide = 2;
while N!= 1 :
    if N%divide != 0:
        divide +=1
    else:
        N //= divide
        print(divide)

---

• 제곱근 활용하기

https://dev-ku.tistory.com/278

import math

N = int(input())

def optimized_prime(N):
    # 2로 나누기 (짝수)
    while N % 2 == 0:
        print(2)
        N //= 2

    # 3부터 sqrt(n)까지의 홀수로 나누기
    for i in range(3, int(math.sqrt(N)) + 1, 2):
        while N % i == 0:
            print(i)
            N //= i

    # 남은 수가 소수인 경우 출력
    if N > 1:
        print(N)

# 최적화된 소인수분해 함수 호출
optimized_prime(N)