[python/파이썬] 백준 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보다 작은 범위 내에서 소수를 구하고 그 소수들로 나누는 것을 생각했다.

작은 수부터 해서 그 수로 나눠질 수 없을 떄까지 나누고 그다음 수로 넘어가서 또 끝까지 나누는 방식을 생각했으나 시간이 너무 오래 걸려서 결과가 나오지 않았다.

다른 코드를 찾아보니 그냥 2부터 1씩 증가시키면서 나누는 코드로 되어있었다. 그러면 소수가 아닌 숫자로도 나눠질 텐데라고 생각했는데 예를 들어서 4라고 치면 이미 2일 때 다 나눠졌으므로 4로 나눴을 때 나눠질 리가 없다.

쉬운 문제인데 이걸 생각하지 못해서 너무 돌아간 문제이다.

 

[소스 코드]

너무나도 간단한 문제인데 소수에 집착하다가 오히려 어렵게 접근하게된 문제이다.

n = int(input())
if n == 1: #n이 1이면 아무것도 출력하지 않음
    print('')

for i in range(2,n+1): #2부터 n까지의 숫자로 나눔
    while n%i==0: #제일 작은수(2)부터 시작해 나눌 수 있을 때까지 나눔
        n/=i #나눠진다면 n의 값을 바꾸고
        print(i) #i를 출력