[백준 16536] 어려운 소인수분해 - 에라토스테네스의 체/python

문제.

16563번: 어려운 소인수분해

소인수 분해 쉬운거 아냐?
소인수 분해의 어려움을 알려주고자 2 - 500만 사이의 수를 소인수 분해 하는 문제

 

첫줄에 자연수의 개수 N이 주어진다.
둘째 줄에 자연수가 N개 공백으로 구분되어 주어진다. 자연수의 범위는 2-5_000_000

N줄에 걸쳐서 자연수의 소인수들을 오름차순으로 출력하면 된다.

입출력 예시.

<입력 예시>
5
5 4 45 64 54

<출력 예시>
5
2 2
3 3 5
2 2 2 2 2 2
2 3 3 3

조건.

1 <= N <= 10^6

2 <= k <= 5 * 10^6

시간제한 2

---

풀이.

소인수의 범위도 500만으로 꽤나 크고, 갯수 역시 100만개가 주어진다.

소수를 구하는 유명한 방법인 에라토스테네스의 체가 있다.
방법은 아주 간단하다.

2부터 오름차순으로 검사하여 이후에 배수들을 모두 제거한다.
제거되지 않은 수는 소수임이 보장된다.

범위의 제곱근 범위까지만 탐색해도 남은 수는 모두 소수임을 알 수 있다.
만약 N까지의 범위에서 N^0.5보다 더 큰 소인수(P)가 존재한다면 N = P*(A)를 성립하는 P와 A가 존재한다는 의미이다.
이때 P가 N^0.5보다 크므로 A는 N^0.5보다 작은 수가 되어 이전에 A의 배수를 제거할 때 P는 제거되었어야 한다.
따라서 탐색범위는 2 - N^0.5면 된다.

소인수 P의 배수를 검사할 때 역시 같은 원리로 P배 이후의 배수들만 확인하여 탈락시킬 수 있다.
P의 배수 탐색범위는 P^2 - N^0.5 까지 P만큼 더해가며 할 수 있다.

따라서 에라토스테네스의 체를 활용하면 해당 범위의 모든 소수를 O( N(log(logN)) )의 시간에 확인할 수 있다.
NlogN 만 해도 거의 선형에 가깝다. 빠른 속도로 접근할 수 있다.

범위안의 배열에 가장 작은 소인수를 적어두면 반복문으로 쉽게 모든 소인수에 접근할 수 있다.
자연스럽게 문제의 조건처럼 오름차순 정렬된 소인수를 만날 수 있다.

제출 코드

import sys; input = sys.stdin.readline

sieve = [i for i in range(5_000_001)]
def s(): #필요한 소수 리스트 만드는 함수
    for i in range(2,int(5_000_001**0.5)+1):
        if sieve[i]==i:
            for j in range(i**2,5_000_001,i):
                if sieve[j] == j: sieve[j] = i
s()
N = int(input())
A = list(map(int,input().split()))

def solve(k): 
    ans = f'{sieve[k]}'
    while k > sieve[k]: # sieve[k] == k가 될 때 멈춘다.
        k //= sieve[k] # 가장작은 소인수로 나누어 주며 탐색
        ans += f' {sieve[k]}'
    return ans

for k in A:
    print(solve(k))

---

s라는 함수를 실행하는데 왜 전역변수를 사용하지 않아도 되는지는 파이썬의 리스트가 구현된 특징 때문인데 아래 글을 보면 더 잘 이해할 수 있다.

[자료구조] Python list / 리스트, 배열 차이 / 시간복잡도

변수의 메모리주소를 담아놓는 특징 덕분에 따로 전역변수 취급하지 않아도 해당 값에 접근할 수 있다.
하지만 리스트의 이름을 바꾸거나 하는 일에 예상치 못한 동작을 할 수 있으므로
해당 문제처럼 간단한 사용이 아닐 경우에는 따로 지역변수처럼 관리해 주는 것이 좋을 수도 있다.

+ 입력을 받고 sieve를 만드는 제출과
   sieve를 만들어두고 입력을 받는 제출의 시간차이가 약 1초정도 발생했다.
   파이썬의 메모리 관리 때문에 발생한 차이가 아닐까 추측된다.

+ 출력을 \n으로 구분해 모아뒀다가 한번에 출력하려 하니 시간초과가 발생했다.
   변수가 너무 길어져서 오래 걸린건지, 확인하지 못했다. 리스트에 담아뒀다 출력하는 방법으로 검사해 볼 수 있겠다.

+ 소인수 분해를 하는 solve 함수의 경우는 소인수의 수 만큼 while문을 반복하게 되는데
   이것은 많아도 20회정도이다. 2^20이 10**6정도로 수가 아무리 커져도 얼마 걸리지 않는다.
   소수를 모아둔 집합을 얼마나 빠르게 만들 수 있는지가 중요할 것.