欧拉筛与欧拉函数

如今我才知道欧拉筛和欧拉函数之间的关系。之前我欧拉函数离线打表一直是n²，亏我一直不T。

先放个纯欧拉筛。prime[1~cnt]记录了cnt个素数，而vis[i]=false表示这个数是素数。

 1 const int MAXN=3000001;
 2 int prime[MAXN];//保存已经求出的素数
 3 bool vis[MAXN];//判断是不是素数
 4 int Prime(int n)
 5 {
 6     int cnt=0;
 7     memset(vis,0,sizeof(vis)); //vis[]=0指是素数
 8     for(int i=2;i<n;i++)
 9     {
10         if(!vis[i])
11         prime[cnt++]=i;
12         for(int j=0;j<cnt&&i*prime[j]<n;j++)
13         {
14             vis[i*prime[j]]=1;
15             if(i%prime[j]==0)//欧拉筛法的精髓之处，目的是为了不重复筛除数据
16             break;
17         }
18     }
19     return cnt;//返回小于n的素数的个数
20 }

再放个线性的欧拉函数板子，内置欧拉筛。

phi[i]表示i的欧拉函数。

 1 const int N=1e7;
 2 int phi[N+10],prime[N+10],tot,ans;
 3 bool mark[N+10];
 4 void getphi()    {
 5    int i,j;
 6    phi[1]=1;
 7    for(i=2;i<=N;i++){
 8        if(!mark[i]){
 9              prime[++tot]=i;//筛素数的时候首先会判断i是否是素数。
10              phi[i]=i-1;//当 i 是素数时 phi[i]=i-1
11              }
12        for(j=1;j<=tot;j++){
13           if(i*prime[j]>N)  break;
14           mark[i*prime[j]]=1;//确定i*prime[j]不是素数
15           if(i%prime[j]==0){//接着我们会看prime[j]是否是i的约数
16              phi[i*prime[j]]=phi[i]*prime[j];break;
17           }
18           else phi[i*prime[j]]=phi[i]*(prime[j]-1);//其实这里prime[j]-1就是phi[prime[j]]，利用了欧拉函数的积性
19        }
20    }
21 }
22 //调用时，给出getphi();即可，mark[i]是false说明是素数，否则是合数