线性筛

int prime[maxn],isprime[maxn]; int num; void getprime() { memset(prime,0,sizeof(prime)); memset(isprime,1,sizeof(isprime)); for(int i=2;i<=n;i++) { if(isprime[i]) prime[num++]=i; for(int j=0;j<num&&i*prime[j]<=n;j++) { isprime[i*prime[j]]=0; if(i%prime[j]==0)break; } } }

我们可以直观地举个例子。i=2 * 3 * 5

此时能筛除 2 * i ,不能筛除 3 * i

如果能筛除3 * i 的话，当 i 等于 i=3 * 3 * 5 时，筛除2 * i 就和前面重复了。

相当于筛了两遍2 * 3 * 3 * 5

下面是欧拉筛

int prime[maxn],isprime[maxn]; int phi[maxn]; int num; void getphi() { memset(prime,0,sizeof(prime)); memset(isprime,1,sizeof(isprime)); phi[1]=1; for(int i=2;i<=n;i++) { if(isprime[i]) { phi[i]=i-1; prime[num++]=i; } for(int j=0;j<num&&i*prime[j]<=n;j++) { isprime[i*prime[j]]=0; if(i%prime[j]==0){phi[i*prime[j]]=phi[i]*prime[j];break;} else phi[i*prime[j]]=phi[i]*phi[prime[j]]; } } }