[백준 11653번] 소인수분해(파이썬)

문제

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

 

입력

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

출력

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

 

예제 입력 1

72

예제 출력 1

2
2
2
3
3

 

예제 입력 2

9991

예제 출력 2

97
103

 

---

 

풀이

소인수분해 : 1보다 큰 자연수를 소인수(소수인 인수)들만의 곱으로 나타내는 것 또는 합성수를 소수의 곱으로 나타내는 방법

1보다 크다고 했으니 2부터 시작하는 걸 생각하고, 그 중 나눠지는 가장 작은 수 부터 나눠주기를 반복합니다.

주어진 수가 72이고, 소인수분해를 한다고 하면
2 x 2 x 2 x 3 x 3이 됩니다.

소인수분해가 되는 과정은
72 / 2 = 36 → 36 / 2 = 18 → 18 / 2 = 9
9는 2로 나눠지지 않기에 다음 소수로 넘어가게 됩니다.
9 / 3 = 3 → 3 / 3 = 1 (1이 되면 소인수분해 종료)

주어진 수가 9991이고, 소인수분해를 한다고 하면
9991이 나눠지는 제일 작은 소수를 구해야 하네요
2부터 나눠지는 소수가 나올 때까지 반복해야 하죠.
9991 / 97 = 103 → 103 / 103 = 1 (1이 되면 소인수분해 종료)

코드를 순서대로 작성한다면
1. 자연수 입력
2. 나눠 줄 변수를 선언 (2부터 시작)
3. 자연수가 1이 될 때까지 반복
5. 자연수와 변수가 나눠진다면 변수를 출력
    5-1. 자연수를 변수로 나눈 몫으로 초기화
6. 나눠지지 않는다면 나눠 줄 변수를 하나씩 증가

---

작성 코드

N = int(input())
X = 2

while N != 1: # 1이 아니면 반복
    if N % X == 0:
        print(X)
        N /= X # 나눈 몫을 N에 초기화
    else:
        X += 1 # 나눌 변수를 하나씩 늘려서 나누기를 반복