[파이썬] 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

---

일단 소인수분해는, 합성수를 소수들의 곱으로 나타내는것을 말한다.

 

1보다 큰 어떤 정수 N이 주어졌을 때, 10진법 표기에서 약수를 찾는 방법들이 몇가지 있다.

 

1. 배수 판정법

정수 N에 대해서,
2의 배수: 일의 자리 숫자가 짝수.
3의 배수: 각 자릿수의 합이 3의 배수.
4의 배수: 맨 뒤 두 자리가 00 또는 4의 배수.
5의 배수: 일의 자리가 0(짝수인 경우) 이나 5(홀수인 경우).
6의 배수: N이 2의 배수이면서 3의 배수.
8의 배수: 맨 뒤 세 자리가 000 또는 8의 배수.
9의 배수: 각 자릿수의 합이 9의 배수.
10의 배수: 일의 자리가 무조건 0.
10^n의 배수 가장 끝의 n개의 자리가 모두 0.
7, 11, 13의 배수: 일의 자리부터 세 자리씩 끊은 뒤, 각 부분을 교대로 빼고 더한 값이 7, 11, 13의 배수.
15의 배수: N이 5의 배수이면서 3의 배수.
25의 배수: 맨 뒤 두 자리가 00 또는 25의 배수(25, 50, 75)
12의 배수: N이 3의 배수이면서 4의 배수.
20의 배수: N이 4의 배수이면서 5의 배수.
30의 배수: N이 5의 배수이면서 6의 배수.
48의 배수: N이 3의 배수이면서 16의 배수.
72의 배수: N이 8의 배수이면서 9의 배수.
27, 37의 배수: 일의 자리부터 3자리씩 끊은 뒤 이들을 모두 합한 결과가 27, 37의 배수인 수.

보다 일반적으로 n이 합성수이고, 소인수가 2개 이상일 때, n의 배수를 판별하는 방법은 d가 n의 유니타리 약수라고 했을 때 d와 n/d의 공배수여야 하므로 이 둘의 배수판정법을 동시에 만족해야 한다는 것이다.

 

2.

모든 합성수는 그 수의 제곱근보다 작거나 같은 약수를 갖는다.

따라서 어떤 큰 수를 소인수분해할때, 그 수의 제곱근보다 큰 수로 나눌 필요가 없다는 사실을 알 수 있다.

---

처음 생각을 할때, 미리 소수테이블을 만든다음, 그 소수테이블을 활용해 소인수분해를 하는 로직을 생각했다.

 

예를들어 2^16보다 작은 소수는 6542개인데, 이를 미리 배열에 저장해 두면, 42억(=2^32) 보다 작은 수는 겨우 6542번 나누어 보기만 하면 소수인지 판정하거나, 1개 이상의 소인수를 구할 수 있는것이다.

 

따라서 에라토스테네스의 체를 사용해서 2부터 입력받은 수 까지의 범위 내에서의 소수들로만 이루어진 리스트를 만들고, 그 리스트를 사용해서 입력받은 수를 나누며 소인수분해를 하는 코드를 짰다.

 

정상적으로 결과는 나왔지만, 백준 파이썬3 기준, 시간초과(1초 제한)이 나와서, 에라토스테네스의 체 로직을 빼고, 그냥 2부터 쭉 나누는걸로 수정을 했다.

---

import math
def solve(x):
    # #에라토스테네스의 체를 사용해서 소수 리스트 생성
    #시간초과때문에 해당 로직은 제외하고 그냥 전부다 돌리기로...
    # tempList = list(range(2, x))
    #
    # for i in range(2, math.ceil(math.sqrt(x))):
    #     for temp in tempList:
    #         if temp/i==1:
    #             pass
    #         elif temp%i==0:
    #             tempList.remove(temp)

    #만든 소수 리스트로 입력받은 수를 나눠보자! -> 위의 이유로 소수 리스트가 아닌 전부다!
    dev = x
    while dev!=1:
        for value in range(2, x+1):
            if dev % value == 0:
                print(value)
                dev = dev // value
                break


if __name__ == "__main__":
    a = int(input())
    solve(a)