[백준 11653] 소인수분해

문제

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

 

입력

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

 

출력

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

---

접근

소인수분해는 합성수를 소수의 곱으로 나타내는 것이다.

그래서 정수 N이 주어졌을 때 2부터 계속 나눠간다. 

이후 2로 나누어 떨어지지 않는다면 수를 증가시켜 3으로 나눈다.

3으로 나누어 떨어지지 않는다면 4로 나누지만 이전에 2로 모두 나눴기 때문에 4로 나누어 떨어지지 않을 것이며 바로 5로 갈것이다.

이러한 원리로 N이 1이 될 때까지 반복한다.

 

구현

입력받은 N을 n으로 계속 나눠주며 나누어 떨어지지 않을 때 n을 증가시킨다.

N = int(input())
n = 2
while N > 1:
    if N%n == 0:
        N //= n
        print(n)
    else:
        n += 1