[백준 11653] 기본 수학 2 - 소인수분해

문제

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

입력

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

출력

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

 

예제 입력 1 72	예제 출력 1 2 2 2 3 3
예제 입력 2 3	예제 출력 2 3
예제 입력 3 6	예제 출력 3 2 3
예제 입력 4 2	예제 출력 4 2
예제 입력 5 9991	예제 출력 5 97 103

 

풀이

 

주어진 N이 2 이상일 때, 2부터 나누어 나누어 떨어지는 수를 출력한다.

 

그리고 나누어주는 수를 다시 2로 초기화하여 계산한다.

 

최적화는 고려하지 않았다.

 

만약 고려해야 할 경우, 가장 마지막으로 분해한 소인수보다 작은 수는

 

반복에서 제외하는 등의 방법을 활용할 수 있겠다.

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