BOJ 16563 - 어려운 소인수분해 (Python3)

소인수분해는 프로그래머들과 뗄려야 뗄 수 없는 관계이다.

RSA를 통한 암호와 복호화는 지금도 광범위하게 쓰이고 있고, 따라서 해커들에게는 더 빠른 소인수분해가, 보안 책임자들에게는 더 큰 소수가 필요하다.

범위가 정해진 많은 수의 소인수분해를 빠르게 할 수 있는 방법으로 N 이하의 수로 모두 나눠 보는 무식한 방법인 에라토스테네스의 체가 있다.

그리고 이 글에서 소개할 방법은 그 무식한 방법을 응용한 linear seive이다.

에라토스테네스의 체는 시간복잡도가 \(O(N\log\log N)\)이고 linear seive는 시간복잡도가 \(O(N)\)이라고 한다.

매우 큰 수에 대해서는 둘 다 시간을 많이 잡아먹기는 하겠지만, 5,000,000 정도의 매우 작은 수들에 대해서는 후자가 상당히 효율적이다.

 

그럼 본격적으로 풀이에 돌입해 보자.

---

문제

지원이는 대회에 출제할 문제에 대해서 고민하다가 소인수분해 문제를 출제해야겠다고 마음을 먹었다. 그러나 그 이야기를 들은 동생의 반응은 지원이의 기분을 상하게 했다.

¶ "소인수분해? 그거 너무 쉬운 거 아니야?"

지원이는 소인수분해의 어려움을 알려주고자 엄청난 자신감을 가진 동생에게 2와 500만 사이의 자연수 N개를 주고 소인수분해를 시켰다. 그러자 지원이의 동생은 기겁하며 쓰러졌다. 힘들어하는 지원이의 동생을 대신해서 여러분이 이것도 쉽다는 것을 보여주자!

 

입력

첫째 줄에는 자연수의 개수 N (1 ≤ N ≤ 1,000,000)이 주어진다.

둘째 줄에는 자연수 ki (2 ≤ \(k_i\) ≤ 5,000,000, 1 ≤ i ≤ N)가 N개 주어진다.

 

예제 입력)

5
5 4 45 64 54

 

출력

N줄에 걸쳐서 자연수 \(k_i\)의 소인수들을 오름차순으로 출력하라.

 

예제 출력)

5
2 2
3 3 5
2 2 2 2 2 2
2 3 3 3

 

---

내 코드

prime = [i for i in range(5000001)]
for i in range(2, 2250):
    if prime[i] == i:
        for j in range(i*2, 5000001, i):
            if prime[j] == j: prime[j] = i

def factorize(N):
    arr = []
    while N > 1:
        arr.append(str(prime[N]))
        N = N // prime[N]
    print(" ".join(arr))
    
    
x, l = input(), map(int, input().split())
for i in l:
    factorize(i)

 

우선 factorize 함수가 실행되기 전에 먼저 prime이라는 배열에 이 수가 소수인지 아닌지를 저장할 수 있는 지표를 저장해야 한다.

어차피 범위는 정해져 있고, 돌려야 할 수가 100만개나 되니까 미리 이 수의 소인수분해를 가능하게 하는 지표를 넣어 주는 쪽이 빠르다.

항상 명심해야 할 것은, 나머지를 구하는 것보다는 배수를 구하는 것이 훨씬 빠르다는 것.

 

먼저 배열 하나를 장만한다. i번째 인덱스의 값이 i가 되도록 말이다. 그러면 장만한 배열은 [0, 1, 2, ..., 4999999, 5000000]이 된다.

그 다음 에라토스테네스의 체를 돌릴 때처럼 √5000000 이하의 정수 i (넉넉잡고 2249까지만 돌려 주었다.)에 대해서 반복문을 돌리되, i에 아직 아무 값도 덮어씌워지지 않았다면 i를 소수로 간주할 것이다.

만약 소수가 아니었으면, 아래의 과정을 통해 i의 가장 작은 소인수 p에 대해, prime[i] = p라고 저장이 완료되었을 것이다.

소수 i에 대해서는, i의 배수 j에 아직 아무 값도 덮어씌워지지 않았다면 prime[j] = i로 만드는 연산을 해 준다.

그렇게 모든 i에 대해서 돌려 준다면, prime[n]이 n의 가장 작은 소인수가 되는 prime이란 배열이 탄생하게 된다.

 

이제 이 배열을 통해서 할 일은 아주 간단하다.

소인수들을 저장할 배열을 만들고, 입력받은 n이 1이 될 때까지 배열에 prime[n]을 저장하고 n을 prime[n]으로 나눈 몫을 n에 저장하는 것을 반복하면 끝.

그 다음 공백 한 칸으로 구별하여 모든 소인수를 한 줄에 출력하면 끝.

 

이로서 16563번의 풀이를 마친다.

그럼, 오늘도 당신의 코딩 실력이 상승하기를.