线性筛求质数
#include <cstring> using namespace std; int prime[1100000],primesize,phi[11000000]; bool isprime[11000000]; void getlist(int listsize) { memset(isprime,1,sizeof(isprime)); isprime[1]=false; for(int i=2;i<=listsize;i++) { if(isprime[i])prime[++primesize]=i; for(int j=1;j<=primesize&&i*prime[j]<=listsize;j++) { isprime[i*prime[j]]=false; if(i%prime[j]==0)break; } } }求欧拉函数
void getlist(int listsize) { memset(isprime,1,sizeof(isprime)); isprime[1]=false; for(int i=2;i<=listsize;i++) { if(isprime[i]) { prime[++primesize]=i; phi[i]=i-1; } for(int j=1;j<=primesize&&i*prime[j]<=listsize;j++) { isprime[i*prime[j]]=false; if(i%prime[j]==0) { phi[i*prime[j]]=phi[i]*prime[j]; break; } phi[i*prime[j]]=phi[i]*(prime[j]-1); } } }求莫比乌斯函数
mu[1]=1; for (int i=2;i<=size;i++) { if (!mark[i])pri[++tot]=i,mu[i]=-1; for (int j=1;j<=tot&&i*pri[j]<=size;j++) { mark[i*pri[j]]=1; if (i%pri[j]==0){mu[i*pri[j]]=0;break;} else mu[i*pri[j]]-=mu[i]; } }求因子个数
void getphi()//facnum表示因子个数，d表示最小因子幂次，因为每次都被最小的质因子筛掉 { facnum[1]=1; for (int i=2;i<=5000000;i++) { if (!flag[i]) p[++tot]=i,facnum[i]=2,d[i]=1; for (int j=1;j<=tot&&i*p[j]<=5000000;j++) { flag[i*p[j]]=1; if (i%p[j]==0) { facnum[i*p[j]]=facnum[i]/(d[i]+1)*(d[i]+2); d[i*p[j]]=d[i]+1; break; } facnum[i*p[j]]=facnum[i]*facnum[p[j]]; d[i*p[j]]=1; } } }