积性函数与线性筛法

Veröffentlicht am | in

从筛素数算法谈起

埃氏筛法

怎么得到$[1,N]$的所有素数，在很早很早以前（古希腊？）就有了方法。
算法的思想是用当前得到的数去筛掉他的倍数，这样每次遍历到的未被筛掉的数一定是素数。

1
2
3
4
5
6
7
8
9
10
11
12
int prime[MAX_N],tot=0;
bool check[MAX_N];
void getPrime(){
	memset(check,0,sizeof(check));
	for(int i=2;i<MAX_N;i++){
		if(check[i])continue;
		prime[tot++]=i;
		for(int j=2*i;j<MAX_N;j+=i)
			check[j]=1;
	}
}

不难发现，算法的每次会遍历$i$的所有倍数，所以算法的复杂度是调和级数的和，即$O(nlogn)$

欧拉筛法

仔细想想埃氏筛法的过程，就会发现每个数都会被它的所有素因子筛一遍，这样的操作是没有意义的，于是我们考虑一种更高效的筛法，使得每个数只被最小的素因子筛。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int prime[MAX_N],tot=0;
bool check[MAX_N];
void Euler(){
	memset(check,0,sizeof(check));
	for(int i=2;i<MAX_N;i++){
		if(!check[i])prime[tot++]=i;
		for(int j=0;j<tot;j++){
			if(prime[j]*i>=MAX_N)break;
			check[prime[j]*i]=1;
			if(i%prime[j]==0)break;
		}
	}
}

上述的算法由于每个数只被其素数筛掉，所以复杂度是$O(n)$的，故而又叫做线性筛法。

积性函数

定义

对于定义域在正整数的算术函数$f(n)$，若$f(1)=1$，且$f(ab)=f(a)f(b)$，其中$a,b$互质，则称$f(n)$为积性函数，如果$a,b$不互质，则称$f(n)$为完全积性函数。

性质

由算术基本定理，$f(n)$的值只由其素数因子的和其幂决定。
若$f(n)$是积性函数，$g(n)$是积性函数，那么$h(n)=f(n)g(n)$是积性函数
若$f(n)$是积性函数，那么$\sum_d|nf(d)$是积性函数

计算

如何得到积性函数往往是我们想关心的，由于上述性质来看，我们只要能够计算出$n$的最小的质数$p$的幂$k$，那么$f(n)=f(p^k)f(n/p^k)$。
所以问题便是求解一个数的最小素因子和其幂。我们发现欧拉筛法符合我们的要求，每个数只会被最小的素因子给筛掉。
由于素因子的幂不能用上述方法计算，所以只有因地制宜地计算。

常见积性函数