一、线性筛

易发现时间复杂度为 $O(n\sqrt{n})$ 的埃式筛法存在缺陷：一个数有可能被多个质数筛掉。

如 $24$，他在 $2\times 12$ 时被筛了一遍，$3\times 8$ 时又被筛了一遍，十分浪费时间。

线性筛就是让每个数只会被一个质数筛去，这个质数就是被筛的合数的最小质因子。

算法代码：

namespace Eular{
	int prime[N],tot;
	bool isprime[N];
	void eular(int x){
		memset(isprime,true,sizeof isprime);
		isprime[1]=false;
		for(int i=2;i<=x;i++){
			if(isprime[i])prime[++tot]=i;
			for(int j=1;j<=tot and i*prime[j]<=x;j++){
				isprime[i*prime[j]]=false;
				if(!(i%prime[j]))break;
			}
		}
	}
}using namespace Eular;

为什么当 $imodprim{e}_j=0$ 时，就可以进入下一个合数了呢？

举例：当 $i=21$ 时，$prime=\{0,2,3,5,7,11,13,17,19\}$。

当遍历到 $prim{e}_2$ 时，$21=3\times 7$，如果此时不停止 $21$ 的工作，那么下一个被筛的数 $5\times 21=105$ 就是被 $5$ 筛掉的，而显然的，根据线性筛工作的原理，$105$ 应该被 $3\times (7\times 5)$，也就是 $3\times 35$ 筛。

二、欧拉函数

1. 定义

欧拉函数 $\phi (n)$ 表示小于等于 $n$ 且与 $n$ 互质的正整数个数。

如 $\phi (12)=4$（$1$，$5$，$7$，$11$）。

特别的，$\phi (1)=1$。

2. 解法

可以用容斥原理很快的求出来。

如求 $12$ 的，用 $A_i$ 表示小于等于 $12$ 的数中，$i$ 的倍数的个数，那么答案为 $+A_1-A_2-A_3+A_{2\times 3}$。

理解例子后，再求更通用的公式：

分解 $n$ 的质因子，设 $n=p_1^{t_1}{p}_2^{t_2}{p}_3^{t_3}\dots p_m^{t_m}$，其中序列 $p$ 的数全为质数且不重复。

设 $A_i$ 表示小于等于 $n$ 且是 $p_i$ 的倍数的自然数集合，则 $|A_i|=\lfloor {\displaystyle \frac{n}{p_i}}\rfloor$（$1\le i\le m$）。

因 $p$ 序列中全为质数，所以 $p$ 里的所有数互质，所以 $p_i$ 与 $p_j$ 的最小公倍数是 $p_i{p}_j$，所以 $|A_i\cap A_j|={\displaystyle \frac{n}{p_i{p}_j}}$（$i\ne j,1\le i,j\le m$）。

由容斥原理，可得：

3. 定理

（1）. 若 $n$ 是质数，$\phi (n)=n-1$。

因为 $n$ 是质数，那么 $n$ 的分解质因数为：$p=\{n\}$。

$\therefore \phi (n)=n(1-{\displaystyle \frac{1}{n}})=n-1$

（2）. 已知 $q$ 是质数，若 $nmodq=0$，则 $\phi (nq)=q\phi (n)$，否则 $\phi (nq)=(q-1)\phi (n)$。

先证明第一点。

用同第二章第 $2$ 节的方法分解 $n$ 的质因子得到序列 $p$。

$\because nmodq=0$，且 $q$ 是质数，

$\therefore q\in p$。

将 $q$ 从集合 $p$ 中删去。

$\therefore \phi (nq)=nq(1-{\displaystyle \frac{1}{q}})\prod _{i=1}^m(1-{\displaystyle \frac{1}{p_i}})$，

$q\phi (n)=qn(1-{\displaystyle \frac{1}{q}})\prod _{i=1}^m(1-{\displaystyle \frac{1}{p_i}})$。

$\therefore \phi (nq)=q\phi (n)$。

再证明第二点。

同理得到 $p$，但此时 $q\notin p$。

$\therefore \phi (nq)=nq(1-{\displaystyle \frac{1}{q}})\prod _{i=1}^m(1-{\displaystyle \frac{1}{p_i}})=(nq-n)\prod _{i=1}^m(1-{\displaystyle \frac{1}{p_i}})$，

$(q-1)\phi (n)=(q-1)n\prod _{i=1}^m(1-{\displaystyle \frac{1}{p_i}})=(nq-n)\prod _{i=1}^m(1-{\displaystyle \frac{1}{p_i}})$。

$\therefore \phi (nq)=(q-1)\phi (n)$。

三、积性函数

1. 定义

若在正整数域中一个函数 $f(x)$ 对于任意 $gcd(x,y)=1$ 的 $x$，$y$ 都满足 $f(xy)=f(x)f(y)$，则称 $f(x)$ 是一个积性函数。

2. $O(n)$ 求 $\phi (1)\sim \phi (n)$

（1）. 证明 $\phi (x)$ 是积性函数

设 $n$ 与 $m$ 互质，他们的质因子的数列分别是 $pn$，$pm$，且个数分别为 $cntn$，$cntm$。

因为 $n$ 与 $m$ 互质，所以 $pn$ 与 $pm$ 里的数互不相同。

则 $\phi (n)\phi (m)$

$=nm\prod _{i=1}^{cntn}(1-p{n}_i)\prod _{i=1}^{cntm}(1-p{m}_i)$

$=\phi (nm)$。

（2）. 解法

设 $q$ 是 $nq$ 的最小质因子，由第二章第 $3$ 节的定理可得：

$\phi (nq)=\{\begin{array}{cc}n-1& n=q\\ q\phi (n)& nmodq=0\\ (q-1)\phi (n)& nmodq\ne 0\end{array}$

这样就可以一边欧拉筛一边递推了。

namespace Phi{
	int prime[N],tot,phi[N];
	bool isprime[N];
	void getphi(int x){
		memset(isprime,true,sizeof isprime);
		isprime[1]=false;
		phi[1]=1;
		for(int i=2;i<=x;i++){
			if(isprime[i]){
				prime[++tot]=i;
				phi[i]=i-1;
			}
			for(int j=1;j<=tot and i*prime[j]<=x;j++){
				isprime[i*prime[j]]=false;
				if(i%prime[j])phi[i*prime[j]]=(prime[j]-1)*phi[i];
				else{
					phi[i*prime[j]]=prime[j]*phi[i];
					break;
				}
			}
		}
	}
}using namespace Phi;

3. 更多积性函数：$d(x)$

（1）. 定义

（2）. 证明 $d(x)$ 是积性函数

（3）. 解法