소인수분해 심화응용 - linear sieve와 smallest prime factor 알고리즘 익히기
1. 문제
16563번: 어려운 소인수분해 (acmicpc.net)
16563번: 어려운 소인수분해
첫째 줄에는 자연수의 개수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 자연수 ki (2 ≤ ki ≤ 5,000,000, 1 ≤ i ≤ N)가 N개 주어진다.
www.acmicpc.net
500만 이내의 값에 대한 100만개의 수가 주어질때 각각을 소인수분해하는 문제
2. smallest prime factor
smallest prime factor 알고리즘은 어떤 수의 가장 작은 소인수를 찾아 배열에 저장하는 알고리즘이다.
소인수분해를 수행하는 기본 알고리즘은.. p = 2부터 시작해서 $\sqrt{n}$까지 나눠보면서 소인수를 찾는데
#trivial prime factorization
def get_factorization(n):
factor = []
p = 2
while p*p <= n:
while n % p == 0:
n = n//p
factor.append(p)
p = p + 1
if n > 1:
factor.append(n)
return factor
예를 들어서 49를 소인수분해하면, $7 \times 7$인데 p=2부터 시도한다면, 쿼리가 매우 많을때 비효율적일수 있다는 점이다.
그래서 최댓값 이내의 배열에서 해당 수의 가장 작은 소인수를 저장해놓는다면, 트라이하는 경우가 줄어들 것이다.
말 그대로 p=7부터 트라이하면 49를 곧바로 소인수분해할 수 있다.
그러면 이걸 어떻게 찾느냐
에라토스테네스의 체를 약간 변형하면 가능하다
n 이내의 가장 작은 소인수를 찾고 싶다면, 먼저 크기 n+1의 배열을 만들고 i번째 인덱스의 값이 i가 들어가도록 초기화한다.
#smallest prime factor
def get_spf(n):
#각 수의 SPF는 i가 되도록 초기화
spf = [i for i in range(n+1)]
다음, 모든 짝수는 2를 소인수로 가지므로...
#smallest prime factor
def get_spf(n):
#각 수의 SPF는 i가 되도록 초기화
spf = [i for i in range(n+1)]
#모든 짝수는 2를 소인수로 가진다.
for i in range(4,n+1,2):
spf[i] = 2
다음 3부터 $\sqrt{n}$까지 시도해서 SPF를 구하자
만약 spf[i] = i라면... 그러니까 i의 가장 작은 소인수가 i라는 것은.. 이미 i는 소수라는 뜻이고
i의 배수는 모두 i로 나누어 떨어지고, i를 가장 작은 소인수로 가진다.
#smallest prime factor
def get_spf(n):
#각 수의 SPF는 i가 되도록 초기화
spf = [i for i in range(n+1)]
#모든 짝수는 2를 소인수로 가진다.
for i in range(4,n+1,2):
spf[i] = 2
#3부터 n**(1/2)까지 SPF를 계산
for i in range(3,int((n+1)**(1/2))+1):
#i의 가장 작은 소인수가 i라는 것은
#i가 소수이고..
if spf[i] == i:
#i를 제외한 i의 배수는 i로 나누어 떨어지고
for j in range(i*i,n+1,i):
#아직 j의 spf가 계산되지 않았다면..
if spf[j] == j:
#i의 배수인 j는 spf가 i이다.
spf[j] = i
return spf
이걸 이용해서 소인수분해를 해보자.
어떤 수 x가 들어온다면..
spf[x]에는 x의 가장 작은 소인수가 들어있다
그래서 x가 1이 아닐때까지 소인수로 나누는 작업을 수행
#spf를 이용한 소인수분해
def get_factorization(x,spf):
factor = []
while x != 1:
먼저 spf[x]에 가장 작은 소인수가 들어가 있으니 factor에 바로 넣고
#spf를 이용한 소인수분해
def get_factorization(x,spf):
factor = []
while x != 1:
#x의 가장 작은 소인수가 spf[x]에 들어가 있음
factor.append(spf[x])
spf[x]는 x의 소인수이므로, x를 spf[x]로 나눠서 다음 x에 저장
이 과정을 반복하면 결국 x는 1이 되고 반복문을 탈출하면
factor에는 x의 모든 소인수가 들어가있다.
#spf를 이용한 소인수분해
def get_factorization(x,spf):
factor = []
while x != 1:
#x의 가장 작은 소인수가 spf[x]에 들어가 있음
factor.append(spf[x])
#x를 x의 가장 작은 소인수로 나눠서, 다음 x에 저장
x = x//spf[x]
return factor
이렇게 하면 시간복잡도는 쿼리당 O(logN)에 소인수분해를 할 수 있다.
3. linear sieve 알고리즘
기본적인 에라토스테네스의 체 알고리즘은 O(Nlog(logN))으로 알려져있다.
#에라토스테네스의 체
def get_prime(n):
result = [1] * (n+1)
for i in range(2,int((n+1)**(1/2))+1):
if result[i] == 1:
for j in range(i+i,n+1,i):
result[j] = 0
return [i for i in range(2,n+1) if result[i] == 1]
그런데 이렇게 찾으면 중복판별하는 경우가 생겨서 O(N)보다 조금 느리다고 한다
예를 들어 $2\times3\times5$의 경우, 2가 소수여서 $2\times3\times5$는 합성수이니 0으로 지우고
3이 소수여서, (이미 지워졌지만) $2\times3\times5$은 합성수이니 0으로 지우고
5가 소수여서, (이미 지워졌지만) $2\times3\times5$은 합성수이니 0으로 지운다
-----------------------------------------------------------------------------------------------------------------------------------------------
그런데 위에서 설명한 SPF를 찾는 방식으로 소수를 찾는 알고리즘을 linear sieve라고 부르고 O(n)에 가능하다고 한다.
이렇게 중복판별하는 경우를 지우고 싶다.
어떤 수 n의 적당한 소인수 p에 대하여, n = ip라고 하자.
그러면 ip는 소수가 아니므로, 합성수라고 딱 1번만 판단하고, 그 외의 다른 n의 소인수에 대해서는 n이 합성수라고 판별하지 않으면 O(n)에 될 것이다.
그러한 p는 어떤 p일까? 당연히 n의 가장 작은 소인수(smallest prime factor)이다.
고정된 i에 대하여, 이미 판별된 소수 [2,3,5,7,...]과의 곱 2i, 3i, 5i,7i,...를 순회하면서
어차피 이들은 소수가 아니니 체에서 지우고, p가 ip의 최소소인수가 아니면 판별을 멈춘다.
p가 ip의 최소소인수인지는 어떻게 판단을 할까?
소수들의 리스트는 가장 작은 소수부터 들어가있고, 이러한 리스트를 순회하면서 2i,3i,5i,...를 보게 된다.
그런데 순회하다가, i가 p로 나누어떨어진다면 $i = kp$로 될 것이다.
그러한 p를 $p_{0}$라고 하자.
그 다음에 고르는 소수 $p_{1}$은 $p_{0}$보다 크다.
이럴때, $ip_{1}$의 최소소인수는 무엇일까?
$p_{1}$일까?
i가 $p_{0}$로 나누어 떨어지므로, $ip_{1} = kp_{0}p_{1}$이 된다.
그러므로 $p_{1}$보다 작은 어떤 소인수 $p_{0}$가 존재한다.
따라서, 이때도 합성수라고 판단하게 되면 기존 에라토스테네스의 체처럼 중복 판별하게 된다.
그러므로 고정된 i에 대하여 이미 판별된 소수 p들의 리스트를 순회하면서 ip를 체에서 제거한다.
그러다가 i가 p로 나누어 떨어지면, 체에서 지우는 작업을 멈춘다.
#linear sieve
def get_prime(n):
sieve = [1]*(n+1)
prime = []
#2부터 n까지 소수인지 검사
for i in range(2,n+1):
#i가 소수이면
if sieve[i] == 1:
#소수 리스트에 넣고
prime.append(i)
#소수 리스트에 있는 j에 대하여..
#ij는 합성수이고, 이것을 지운다.
#지우면서 ij가 n보다 커지거나
#i가 j의 배수이면 그 다음의 소수는 ij의 최소소인수가 아니므로 멈춘다.
for j in prime:
if i * j > n:
break
sieve[i*j] = 0
if i % j == 0:
break
return prime
당연히 이 linear sieve를 사용하면서 모든 합성수의 최소 소인수를 찾을 수 있다.
이미 설명했듯이 ij의 최소소인수는 j이다.
#linear sieve & spf
def get_prime(n):
sieve = [1]*(n+1)
prime = []
spf = [0]*(n+1)
#2부터 n까지 소수인지 검사
for i in range(2,n+1):
#i가 소수이면
if sieve[i] == 1:
#소수 리스트에 넣고
prime.append(i)
#당연히 소수 i의 최소소인수는 i이다.
spf[i] = i
#소수 리스트에 있는 j에 대하여..
#ij는 합성수이고, 이것을 지운다.
#지우면서 ij가 n보다 커지거나
#i가 j의 배수이면 그 다음의 소수는 ij의 최소소인수가 아니므로 멈춘다.
for j in prime:
if i * j > n:
break
sieve[i*j] = 0
#i*j의 최소소인수는 j이다.
spf[i*j] = j
if i % j == 0:
break
return prime,spf
가장 작은 소인수를 찾는게 좀 중요하지, 소수를 찾는다는 점에서는 그렇게 의미있는것은 아닌듯이라고 어떤 고수의 글을 본 기억이 나는데
4. 풀이1
SPF를 이용해서 가장 작은 소인수를 저장해두고 소인수분해를 수행한다.
from sys import stdin
def get_spf(n):
spf = [0]*(n+1)
spf[1] = 1
for i in range(2,n+1):
spf[i] = i
for i in range(4,n+1,2):
spf[i] = 2
for i in range(3,int((n+1)**(1/2))+1):
if spf[i] == i:
for j in range(i*i,n+1,i):
if spf[j] == j:
spf[j] = i
return spf
def get_factorization(x,spf):
factor = []
while x != 1:
factor.append(spf[x])
x = x//spf[x]
return factor
n = int(stdin.readline())
num = list(map(int,stdin.readline().split()))
spf = get_spf(5000000)
for k in num:
print(*get_factorization(k,spf))
5. 풀이2
그리고 사실 SPF 방법을 쓰지 않아도 그냥 $O(\sqrt{n})$ 알고리즘으로 소수를 찾기만 해도 통과하긴 한다
여기서 중요한 점은 500만 이하의 모든 소수를 찾는게 아니고,
500만이 가질 수 있는 최대 소인수는 500만이 아니고 $\sqrt{5000000}$이기 때문에..
2부터 $\sqrt{5000000}$까지만 소수를 찾는게 중요하다
from sys import stdin
N = 5000000
sieve = [1]*(N+1)
primes = []
for p in range(2,int((N+1)**(1/2))+1):
prime = True
for i in range(2,int((p+1)**(1/2))+1):
if p % i == 0:
prime = False
break
if prime:
primes.append(p)
def get_factorization(k,primes):
factor = []
for p in primes:
if p*p > k:
break
while k % p == 0:
k = k//p
factor.append(p)
if k > 1:
factor.append(k)
return factor
n = int(input())
num = list(map(int,input().split()))
for k in num:
print(*get_factorization(k,primes))
그리고 소인수분해할때 주의할 점이
그냥 p=2부터 트라이하는 소인수분해는 쉽게 작성하는데
p=2부터 1씩 증가시키면서 하지 않고 위와 같이 소수가 저장된 배열에서 소인수분해하면
이런식으로 작성해가지고 시간초과 받았는데
def prime_factorization(n,prime_list):
prime = []
for p in prime_list:
if n == 1:
break
else:
if n % p == 0:
while n % p == 0:
n = n//p
prime.append(p)
return prime
기본 소인수분해랑 비교해보면 뭐가 문제인지 느낌이 오겠지
소수로만 나누면.. n == 1이 될수도 있지만
n == 1이 안되고 이미 prime_list에서 지나버린 어떤 소수만 남을수 있거든
그러면 모든 prime_list를 돌더라도 소인수분해가 안끝날수 있지
#trivial prime factorization
def get_factorization(n):
factor = []
p = 2
while p*p <= n:
while n % p == 0:
n = n//p
factor.append(p)
p = p + 1
if n > 1:
factor.append(n)
return factor
참조
Prime Factorization using Sieve O(log n) for multiple queries - GeeksforGeeks
Prime Factorization using Sieve O(log n) for multiple queries - GeeksforGeeks
A Computer Science portal for geeks. It contains well written, well thought and well explained computer science and programming articles, quizzes and practice/competitive programming/company interview Questions.
www.geeksforgeeks.org
https://ahgus89.github.io/algorithm/Linear-sieve/
Linear-sieve
O(n)에 해결하자!
ahgus89.github.io
https://www.geeksforgeeks.org/sieve-eratosthenes-0n-time-complexity/
Sieve of Eratosthenes in 0(n) time complexity - GeeksforGeeks
A Computer Science portal for geeks. It contains well written, well thought and well explained computer science and programming articles, quizzes and practice/competitive programming/company interview Questions.
www.geeksforgeeks.org
'정수론' 카테고리의 다른 글
| 골드바흐의 추측을 알고리즘 문제에 적용하는 방법 (0) | 2023.02.06 |
|---|---|
| 팩토리얼(factorial)의 비밀 - 스털링 근사 공식과 자리수 계산하기 (0) | 2023.01.02 |
| 중국인의 나머지 정리(Chinese Remainder Theorem) 기본 이해하기 (0) | 2022.12.30 |
| 약수의 합과 약수의 개수 공식 익히기 (0) | 2022.12.26 |
| 컴퓨터가 등비수열의 합을 구하는 방법 (0) | 2022.12.20 |
