筛法

Summary

筛法用于求素数与积性函数。埃拉托斯特尼筛法从每个素数出发把它的倍数标记为合数，时间复杂度为 O(n log log n)；欧拉筛法即线性筛，让每个合数只被它的最小质因子筛去一次，达到 O(n)，并能在筛的过程中递推积性函数。给出欧拉筛递推欧拉函数、莫比乌斯函数、约数个数函数与约数和函数四种实现，各自按当前数是否被最小质因子整除分两种转移。开头另附三种算法的复杂度对比表。

参考资料

• 筛法 - OI Wiki
• 埃拉托斯特尼筛法 - 维基百科

算法对比

算法名称	时间复杂度
朴素算法	$O(n\sqrt n)$
埃拉托斯特尼筛法	$O(n\log\log n)$
欧拉筛法	$O(n)$

埃拉托斯特尼筛法

埃拉托斯特尼筛法（Sieve of Eratosthenes）简称埃氏筛法。

199 Bcpp

void sieve()
{
	vis[0]=vis[1]=1;
	for(int i=2;i*i<N;i++)
	{
		if(vis[i])continue;
		for(int j=i*i;j<N;j+=i)vis[j]=1;
	}
	int cnt=0;
	for(int i=2;i<N;i++)
	{
		if(vis[i])continue;
		pri[++cnt]=i;
	}
}

欧拉筛法

欧拉筛法（Sieve of Euler）也称线性筛法，让每个合数只被它的最小质因子筛去一次，时间复杂度为 $O(n)$。它还能在筛的过程中递推出欧拉函数、莫比乌斯函数等积性函数。

素数

205 Bcpp

void sieve()
{
	vis[0]=vis[1]=1;
	int cnt=0;
	for(int i=2;i<N;i++)
	{
		if(!vis[i])pri[++cnt]=i;
		for(int j=1;j<=cnt;j++)
		{
			if(i*pri[j]>=N)break;
			vis[i*pri[j]]=1;
			if(i%pri[j]==0)break;
		}
	}
}

数论函数

欧拉函数

$$\varphi(n)=n\prod_{p\mid n}\frac{p-1}{p}$$

328 Bcpp

void sieve()
{
	vis[0]=vis[1]=1;
	phi[1]=1;
	int cnt=0;
	for(int i=2;i<N;i++)
	{
		if(!vis[i])
		{
			pri[++cnt]=i;
			phi[i]=i-1;
		}
		for(int j=1;j<=cnt;j++)
		{
			if(i*pri[j]>=N)break;
			vis[i*pri[j]]=1;
			if(i%pri[j]==0)
			{
				phi[i*pri[j]]=phi[i]*pri[j];
				break;
			}
			phi[i*pri[j]]=phi[i]*phi[pri[j]];
		}
	}
}

莫比乌斯函数

$$\mu(n)= \begin{cases} 1 & n=1 \\ 0 & \exists d>1,d^2\mid n \\ (-1)^{\omega(n)} & \text{otherwise} \end{cases}$$

299 Bcpp

void sieve()
{
	vis[0]=vis[1]=1;
	mu[1]=1;
	int cnt=0;
	for(int i=2;i<N;i++)
	{
		if(!vis[i])
		{
			pri[++cnt]=i;
			mu[i]=-1;
		}
		for(int j=1;j<=cnt;j++)
		{
			if(i*pri[j]>=N)break;
			vis[i*pri[j]]=1;
			if(i%pri[j]==0)
			{
				mu[i*pri[j]]=0;
				break;
			}
			mu[i*pri[j]]=-mu[i];
		}
	}
}

约数个数函数

$$d(n)=\sum_{d\mid n}1=\prod_{i=1}^k(a_i+1)$$

380 Bcpp

void sieve()
{
	vis[0]=vis[1]=1;
	num[1]=d[1]=1;
	int cnt=0;
	for(int i=2;i<N;i++)
	{
		if(!vis[i])
		{
			pri[++cnt]=i;
			num[i]=d[i]=2;
		}
		for(int j=1;j<=cnt;j++)
		{
			if(i*pri[j]>=N)break;
			vis[i*pri[j]]=1;
			if(i%pri[j]==0)
			{
				num[i*pri[j]]=num[i]+1;
				d[i*pri[j]]=d[i]/num[i]*num[i*pri[j]];
				break;
			}
			num[i*pri[j]]=2;
			d[i*pri[j]]=d[i]*2;
		}
	}
}

约数和函数

$$\sigma(n)=\sum_{d\mid n}d=\prod_{i=1}^k\left(1+p_i+p_i^2+\dots+p_i^{a_i}\right)$$

432 Bcpp

void sieve()
{
	vis[0]=vis[1]=1;
	num[1]=sigma[1]=1;
	int cnt=0;
	for(int i=2;i<N;i++)
	{
		if(!vis[i])
		{
			pri[++cnt]=i;
			num[i]=sigma[i]=i+1;
		}
		for(int j=1;j<=cnt;j++)
		{
			if(i*pri[j]>=N)break;
			vis[i*pri[j]]=1;
			if(i%pri[j]==0)
			{
				num[i*pri[j]]=num[i]*pri[j]+1;
				sigma[i*pri[j]]=sigma[i]/num[i]*num[i*pri[j]];
				break;
			}
			num[i*pri[j]]=pri[j]+1;
			sigma[i*pri[j]]=sigma[i]*sigma[pri[j]];
		}
	}
}

例题

洛谷 P3383 【模板】线性筛素数

给定一个范围 $n$，有 $q$ 个询问，每次输出第 $k$ 小的素数。（$n\le10^8,q\le10^6$）

洛谷 P1865 A % B Problem

给定 $n$ 组 $l,r$ 和最大值 $m$，求区间 $[l,r]$ 内质数的个数。（$n\le1000,m\le10^6$）