线性筛（素数筛加欧拉筛）

线性筛

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]];}}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！