백준 > 단계별로 풀어보기 > 약수, 배수와 소수 > 11653번: 소인수분해

문제

정수 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 = int(input())
x = 2
lst = []

while N > 1:
    if N % x == 0:
        lst.append(x)
        N = N // x
    else:
        x += 1

for i in lst:
    print(i)

 

for문으로 하려다가 while문으로 돌린 나 자신 칭찬해!

그리고 처음엔 복잡하게 풀려다가, 파이썬 소인수분해를 검색하고 그 방식을 따라했다.

소인수분해를 하면 2와 3으로 이루어져 있으니 x를 2로 초기화하고 while문을 진행했다.

주어진 입력 N이 x로 나누어 떨어지면 리스트에 x를 추가하고, N은 다음 단계를 실행해야 하니 x로 나눈 몫으로 바꿔주었다.

N이 x로 나누어 떨어지지 않을 경우에는 x를 1 증가시켜 3으로 만들었다.

그리고 출력은 세로로 나와야 하니 리스트를 순회하며 하나씩 출력시켰는데, if문에서 x를 출력시켜도 되었다. 

그리고 해당 코드에는 N이 1인 경우를 넣지 않았지만 정답처리 되었다.

 

N=1인 경우, if문에서 답을 출력하는 경우 모두 합친 코드는 아래에 있다.

리스트를 사용하지 않고 맨 뒤의 for문을 사용하지 않아서 그런가, 코드 길이가 가장 짧다.

 

N = int(input())
x = 2

while N > 1:
    if N == 1:
        break
   
    if N % x == 0:
        N = N // x
        print(x)
    else:
        x += 1