欧拉筛+素数筛+莫比乌斯模板

欧拉筛

const int maxn;
int phi[maxn],prime[maxn];
bool vis[maxn];
void init()
{phi[1]=1;int tot=0;for(int i=2;i<maxn;i++){if( !vis[i] ){ prime[tot++]=i; phi[i]=i-1; }for(int j=0;j<tot&&i*prime[j]<maxn;j++){vis[i*prime[j]]=1;if( i%prime[j]==0 ){phi[i*prime[j]]=phi[i]*prime[j];break;}else phi[i*prime[j]]=phi[i]*(prime[j]-1);}}
}

素数筛

const int maxn;
int prime[maxn];
bool vis[maxn];
void init()
{int tot=0;for(int i=2;i<maxn;i++){if( !vis[i] ) prime[tot++]=i; for(int j=0;j<tot&&i*prime[j]<maxn;j++){vis[i*prime[j]]=1;if( i%prime[j]==0 )break;}}
}

莫比乌斯反演

int p[maxn],mou[maxn];
bool q[maxn];
void init()
{mou[1]=1;int t=0;for(int i=2;i<maxn;i++){if( !q[i] ){ p[t++]=i; mou[i]=-1; }for(int j=0;j<t&&i*p[j]<maxn;j++){q[i*p[j]]=1;if( i%p[j]==0 ){ mou[i*p[j]]=0; break; }mou[i*p[j]]=-mou[i];}}
}