先挖个坑，以后来填。
大佬的讲解连接【】
目前有的筛法有：
- 诶氏筛
- 扩展诶氏筛
- 欧拉筛（筛一类积性函数）
- 杜教筛
- 洲阁筛
- Min_25筛【】
上几份模板代码
- 线性筛素数
P3383#include#include #include using namespace std;const int M=1e7+10;int p[M];bool vis[M];int n,cnt,m;void sift(int a){ vis[0]=vis[1]=1; for(int i=2;i<=a;i++){ if(!vis[i]) p[++cnt]=i; for(int j=1;j<=cnt&&p[j]*i<=a;j++){ vis[p[j]*i]=1; if(i%p[j]==0) break; } }}int a;int main(){ scanf("%d%d",&n,&m); sift(n); for(int i=1;i<=m;i++){ scanf("%d",&a); if(vis[a]) printf("No\n"); else printf("Yes\n"); } return 0;}
- 线性筛欧拉函数和莫比乌斯函数
#include#include #include using namespace std;const int M=1e5+10;int mob[M],prime[M],cnt;bool notp[M];void Mobius(int n){ mob[1]=1; for(int i=2;i<=n;i++){ if(!notp[i]) prime[++cnt]=i,mob[i]=-1; for(int j=1;j<=cnt&&i*prime[j]<=n;j++){ notp[i*prime[j]]=1; if(i%prime[j]){ mob[i*prime[j]]=-mob[i]; }else{ mob[i*prime[j]]=0; break; } } }}int phi[M];void euler(int n){ phi[1]=1; for(int i=2;i<=n;i++){ if(notp[i]) prime[++cnt]=i,phi[i]=i-1; for(int j=1;j<=cnt&&i*prime[j]<=n;j++){ notp[i*prime[j]]=1; if(i%prime[j]){ phi[i*prime[j]]=phi[i]*(prime[j]-1); }else{ phi[i*prime[j]]=phi[i]*prime[j]; break; } } }}可以合在一起写
- 线性筛约数个数与约数个数和
#include#include #include using namespace std;const int M=1e5+10;int prime[M],cnt,gdiv[M],sdiv[M];bool nop[M];int num[M],sp[M];void init(int n){ gdiv[1]=sdiv[1]=1; for(int i=2;i<=n;i++){ if(!nop[i]) prime[++cnt]=i,gdiv[i]=2,num[i]=1,sdiv[i]=sp[i]=1+i; for(int j=1;j<=cnt&&i*prime[j]<=n;j++){ nop[i*prime[j]]=1; if(i%prime[j]){ gdiv[i*prime[j]]=gdiv[i]*gdiv[prime[j]];num[i*prime[j]]=1; sdiv[i*prime[j]]=sdiv[i]*sdiv[prime[j]]; sp[i*prime[j]]=1+prime[j]; }else{ gdiv[i*prime[j]]=gdiv[i]/(num[i]+1)*(num[i]+2);num[i*prime[j]]=num[i]+1; sdiv[i*prime[j]]=sdiv[i]/sp[i]*(sp[i]*prime[j]+1); sp[i*prime[j]]=sp[i]*prime[j]+1; break; } } }}int main(){ init(20); for(int i=1;i<=20;i++){ printf("%d : %d %d\n",i,gdiv[i],sdiv[i]); }}https://blog.csdn.net/ControlBear/article/details/77527115