列出所有数字，从小到大枚举，将枚举数的所有倍数筛掉。复杂度$O(n\log\log n)$，证明见这里。

void sieve(int n){
	int i,j;
	isnp[0]=isnp[1]=1;
	for(i=2;i<=n;i++){
		if(isnp[i])continue;
		pri[cnt++]=i;
		for(j=i;j<=n;j+=i)isnp[j]=1;
	}
}

埃氏筛会将一个合数被其所有质因数都筛一遍，很浪费时间。

考虑优化，让每个合数都只被最大的非本身的因数（和最小质因数共同）筛到一遍。

故首先枚举所有数 $i$ ，再枚举所有 $i$ 的素倍数 $t=pri_j\times i$ ，（ $i$ 与 $pri[j]$ 共同）将 $t$ 筛掉，且当 $pri_j\mid i$ 时退出枚举。此举的正确性在于：

• $i$ 的最小质因数为 $pri[j]$ ；
• $\forall k>j, i\times pri[k]$ 会被比 $i$ 更大的 $\frac{i}{pri[j]}\times pri[k]$ 与 $pri[j]$ 共同筛掉。

因此，欧拉筛的每个数都只被筛了一次，复杂度 $O(n)$ 。

模板题

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

除了筛素数，欧拉筛还可以线性地筛一些积性函数。

欧拉函数 $\varphi(n)$ 表示小于等于 $n$ 且 $\gcd(i,n)=1$ 的 $i$ 个数。

欧拉函数是积性的，也就是对任意 $n,m$ 满足 $(m,n)=1$ ，有 $\varphi(n\times m)=\varphi(n)\times \varphi(m)$ 。有一个不错的证法。

处理边界情况：

• 当 $n=p$ 的时候， $\varphi(n)=p-1$ ；
• 当 $n=p^k$ 的时候， $\varphi(n)=p^{k-1}(p-1)$ ；

因为欧拉函数是积性的，如果将 $n$ 质因数分解为 $n=\prod_i p_i^{k_i}$ ，可以得到：

$$ \begin{aligned} \varphi(n)&=\prod_i p_i^{k_i-1}(p_i-1)\\ &=n\prod_i\frac{p_i-1}{p_i} \end{aligned} $$

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

这里讲过了，不再赘述。