首先有以下性质：(p 为素数)

1. φ（p）=p-1

2. 如果i mod p==0，那么φ( i*p )=p*φ( i )

3. 若i mod p≠0，那么φ（i*p）=φ（i）*（p-1）

证明见，在此表示感谢

典型题目见

#include
     
      //   在筛素数的同时，把欧拉函数求出 #include
      
       #include
       
        #include
        
         #include
         
          #define M 1000001using namespace std;int phi[M],prime[M],tot,ans;bool notp[M];void getphi(){    phi[1]=1;    for(int i=2;i<=M;i++)    {        if(!notp[i])        {            prime[++tot]=i;            phi[i]=i-1;//i是素数         }        for(int j=1;j<=tot&&i*prime[j]<=M;j++)        {            notp[i*prime[j]]=1;//不是素数             if(i%prime[j]==0)// 如果i mod p==0，那么φ( i*p )=p*φ( i )            {                phi[i*prime[j]]=phi[i]*prime[j];                break;//筛素数省时             }            // 若i mod p≠0，那么φ（i*p）=φ（i）*（p-1）            else phi[i*prime[j]]=phi[i]*(prime[j]-1);        }    }    return;}int main(){    getphi();    for(int i=1;i<=100;i++)    {        printf("%d %d\n",i,phi[i]);    }    return 0;}