Linear-sieve
본 글은 Codeforces 블로그 글을 많이 참고하여 작성된 글이다.
영어가 된다면 원본 글도 읽어보면 좋다.
이 글에서 쓰이는 $p$는 별 말이 없으면 소수를 나타낸다.
소수 판별
$1$부터 $n$까지, 각 수가 소수인지 아닌지 구하고 싶다. 이 문제를 해결하는 간단하고도 빠른 알고리즘으로는 에라토스테네스의 체가 잘 알려져 있다.
$i$를 $2$부터 $n$까지 증가시키면서, $i$가 합성수가 아니라면 소수이고, 그 때 $i$의 배수들은 합성수이다.
이 내용을 그대로 구현하면 다음과 같은 코드를 얻는다.
bool isp[sz];
void era(int n)
{
memset(isp, 1, sizeof isp);
for(int i=2;i<=n;i++)
if(isp[i])
for(int j=2;i*j<=n;j++)
isp[i*j]=0;
}
시간복잡도는 어떻게 될까? $i$가 소수일 때 마다 $n \over i$번 내부 반복문을 돌게 된다.
$O(\displaystyle \sum_{p < n} {n \over p}) = O(n \log \log n)$임이 알려져 있고, 따라서 시간복잡도는 $O(n \log \log n)$이 된다.
시간복잡도의 개선
해봐야 크기 $n$짜리 배열을 채우는데 $O(n)$에 할 수는 없을까?
에라토스테네스의 체가 $O(n)$이 아닌 이유는, $2 \times 3 \times 5 \times 7$ 같은 수를 생각해 보자.
$2$가 소수이므로 $2$의 배수인 $2 \times (3 \times 5 \times 7)$은 합성수이다.
$3$가 소수이므로 $3$의 배수인 $3 \times (2 \times 5 \times 7)$은 합성수이다.
$5$가 소수이므로 $5$의 배수인 $5 \times (2 \times 3 \times 7)$은 합성수이다.
$7$가 소수이므로 $7$의 배수인 $7 \times (2 \times 3 \times 5)$은 합성수이다.
이와 같이 소인수가 많은 합성수는 여러번 합성수라고 판별되고, 중복 판별 때문에 $O(n)$보다 느린 것이다.
중복을 피하는 방법은 뭐가 있을까? $n$의 적당한 소인수 $p$가 존재하여 $n=ip$라 하면, $p \times i$가 합성수라고 딱 한번만 판별해주고, 그 외의 다른 소인수들에 대해서는 $n$이 합성수라고 판별하지 않으면 가능할 것 같다.
$i$에 따라 $p$를 변화시켜보자. 지금까지 구한 소수들을 보면서, $p$가 특정 조건을 만족하지 않는 순간 반복을 멈추면 될 것이다. 이런 조건을 만족하는 좋은 소인수는 최소소인수 이다.
즉, $2i, 3i, 5i, 7i, …$를 보다가, $p$가 $i \times p$의 최소소인수가 아닌 순간 판별을 멈추면 된다. $i$의 최소소인수는 $p$ 이상이어야 하므로, $p \mid i$일 때 판별을 하고 나면, 그 다음부터는 고르는 소수가 $i$의 최소소인수보다 크게 되므로 $ip$의 최소소인수가 될 수는 없다. 따라서 판별을 종료해주면 된다.
이렇게 되면, 모든 합성수에 대해서 딱 한번씩만(최소소인수는 유일하니까) 판별을 해주게 되고, $O(n)$의 시간복잡도를 얻을 수 있다. 과정을 요약하면 다음과 같다.
i가 합성수가 아니면 소수 목록에 i를 추가한다. 소수 목록에 있는 j에 대해, ij는 합성수이고, i가 j의 배수이면 멈춘다.
역시 그대로 구현하면 간단한 코드를 얻는다.
vector<int> p; //소수 목록
bool isp[sz];
void linear_sieve(int n)
{
memset(isp, 1, sizeof isp);
for(int i=2;i<=n;i++)
{
if(isp[i]) p.push_back(i);
for(auto j: p)
{
if(i*j>n) break;
isp[i*j]=0;
if(i%j==0) break;
}
}
}
에라토스테네스의 체에 비해 유의미하게 빠르게 작동한다.
그리고 소수가 담긴 벡터를 덤으로 얻을 수 있다.
이 과정을 생각해보면, 모든 합성수에 대해서 최소소인수를 바로 알아낼 수 있다. $ij$의 최소소인수는 $j$이다.
vector<int> p;
int sp[sz];
void linear_sieve(int n)
{
for(int i=2;i<=n;i++)
{
if(!sp[i]) p.push_back(i);
for(auto j: p)
{
if(i*j>n) break;
sp[i*j]=j;
if(i%j==0) break;
}
}
}
다음과 같이 코드를 수정하면, $sp[i]$는 $i$가 소수이면 $0$, 아니면 최소 소인수를 담고 있다.
이를 통해 작은 수를 여러 번 소인수분해 하는 것을 쉽게 할 수 있다. $sp[i]$가 0이 아닐 때 까지 $i$를 $sp[i]$로 나누어주면 된다. 이 문제를 통해 연습해보자. 정답 코드
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
int n, m, k, ans;
const int mod=1e9+7;
vector<int> p;
const int sz=5050505;
int sp[sz];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
int i, j, temp=0;
for(i=2;i<sz;i++)
{
if(!sp[i]) p.push_back(i);
for(auto j:p)
{
if(i*j>=sz) break;
sp[i*j]=j;
if(i%j==0) break;
}
}
cin>>n;
while(n--)
{
cin>>i;
while(sp[i]) cout<<sp[i]<<' ', i/=sp[i];
cout<<i<<'\n';
}
}
multiplicative function의 계산
Linear sieve는 훨씬 강력한 기능을 할 수 있다. 소수 판별은 덤에 가깝다. 특히 소수를 채우는 것 뿐만 아니라 다양한 정수론적 함수들을 $O(n)$에 계산할 수 있다.
곱셈함수나 몇몇 함수의 정의와 성질에 대해서는 이전 글을 참고하도록 하고, 그러면 이런 함수들을 어떻게 구할지 생각해보자.
곱셈함수 $f(n)$에 대해 $f(i)$를 전부 채워넣고 싶다. 어떻게 하면 좋을까? 쉬운 경우부터 생각해보자.
$f(1) = 1$이고, $f(p)$는 보통 $O(1)$에 계산된다.
합성수의 경우는? 서로소인 $n, m$에 대해 $f(nm) = f(n)f(m)$이니 이런 $n, m$만 찾으면 이전에 구한 정보를 가지고 역시 $O(1)$에 계산이 될 것이다.
위에서 사용한 Linear sieve를 잘 살펴보면, $n=ip$에서 $p \nmid i$이면 당연히 $gcd(i, p)=1$이므로 $f(n) = f(i)f(p)$로 $O(1)$에 계산해줄 수 있다. $p \mid i$인 경우도 $p$가 소수이기 때문에 대부분 간단한 관계식이 성립한다.
예를 들어, $\phi(ip) = p\phi(i)$, $\mu(ip) = 0$ 같은 간단한 관계식이 성립한다. 따라서 $\phi(n)$이나 $\mu(n)$도 $O(n)$에 전부 구해줄 수 있다.
물론 모든 함수가 $p$와 $i$만의 관계식으로 표현되지는 않는다. $\tau(n)$이나 $\sigma(n)$의 경우 $p$에 대한 지수에 의존한다. 이런 경우는 간단하게 그 지수 역시 구해주면 된다. $p \nmid i$ 이면 지수는 $e_n=1$이고, $p \mid i$ 이면 지수는 $e_n=e_i + 1$이다.
이렇게 구한 지수를 바탕으로 $p \mid i$일 때 $\tau(n) = \tau(i) \times {(e_n + 1) \over e_n}$, $\sigma(n) = \sigma(i) \times {(p^{e_i + 1}-1) \over (p^{e_i}-1)}$의 관계식을 이용해 계산해줄 수 있다. 다음은 $\phi(n), \mu(n), \tau(n), \sigma(n)$을 계산하는 코드이다. 코드
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
int n, m, k, ans, mod=1e9+7;
int pw(int a, int b)
{
int ret=1;
while(b)
{
if(b&1) ret*=a;
a*=a;
b>>=1;
}
return ret;
}
vector<int> p;
const int sz=101010;
int sp[sz], e[sz], phi[sz], mu[sz], tau[sz], sigma[sz];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
int i, j, temp=0;
phi[1]=mu[1]=tau[1]=sigma[1]=1;
for(i=2;i<sz;i++)
{
if(!sp[i])
{
p.push_back(i);
e[i]=1;
phi[i]=i-1;
mu[i]=-1;
tau[i]=2;
sigma[i]=i+1;
}
for(auto j:p)
{
if(i*j>=sz) break;
sp[i*j]=j;
if(i%j==0)
{
e[i*j]=e[i]+1;
phi[i*j]=phi[i]*j;
mu[i*j]=0;
tau[i*j]=tau[i]/e[i*j]*(e[i*j]+1);
sigma[i*j]=sigma[i]*(j-1)/(pw(j, e[i*j])-1)*(pw(j, e[i*j]+1)-1)/(j-1);//overflow
break;
}
e[i*j]=1;
phi[i*j]=phi[i]*phi[j];
mu[i*j]=mu[i]*mu[j];
tau[i*j]=tau[i]*tau[j];
sigma[i*j]=sigma[i]*sigma[j];
}
}
for(i=2;i<sz;i++)
cout<<i<<' '<<e[i]<<' '<<phi[i]<<' '<<mu[i]<<' '<<tau[i]<<' '<<sigma[i]<<'\n';
}
이렇게 Linear sieve는 $O(n)$에 $1$부터 $n$ 까지의 소수 판별, 곱셈함수 $f(n)$ 구하기를 해낼 수 있는 강력한 도구이다. 특히 곱셈함수가 아니더라도, 비슷하게 $i$와 $p$의 관계에 따라 $f(ip)$를 계산할 수만 있다면 역시 Linear sieve를 사용할 수 있다. (위에서 이야기한 최소소인수의 지수가 그 예시이다) 몇몇 정수론 문제는 미리 함수값들을 저장해두면 문제를 쉽게 풀 수 있는 경우가 많으니, Linear sieve를 익혀두면 도움이 될 것이다.