欧拉函数的简单求法及欧拉打表法

欧拉函数的意义为，对于一个正整数n来说，euler（n）即为小于等于n，且与n互斥的数的个数

根据容斥原理可得：

euler（n）=n-n/p1-n/p2....-n/pn+n/p1p2+n/p1p3+n/p2p3...+n/pn-1pn-n/p1p2p3.......

=n(1-1/p1)(1-1/p2)....(1-1/pn)

同样根据积性原理可得:

若m，n互斥则

euler（m*n）=euler(m)*euler(n);

因为n=p1^k1+p2^k2....+pn^kn

所以euler(n)=euler(p1^k1)*euler(p2^k2)*....euler(pn^kn)

因为p为素数的话euler(pn^kn)=pn^kn-pn^(kn-1)=pn^(kn-1)(1-1/pn);

所以euler(n)=n(1-1/p1)(1-1/p2)....(1-1/pn)

计算欧拉函数:

 1  int euler_phi(int n)
 2  {
 3       int m=(int)sqrt(n+0.5);
 4       int ans=n;
 5       for(int i=2;i<=m;i++)
 6           if(n%i==0)//找素因子
 7           {
 8               ans=ans/i*(i-1);
 9               while(n%i==0)n/=i;//除尽
10           }
11      if(n>1)ans=ans/n*(n-1);
12      return ans; 
13  }

打表求欧拉函数:

 1 int phi[maxn];
 2 void phi_table(int n)
 3 {
 4     for(int i=2;i<=n;i++)phi[i]=0;
 5     phi[1]=1;
 6     for(int i=2;i<=n;i++)
 7         if(!phi[i])
 8             for(int j=i;j<=n;j+=i)
 9             {
10                 if(!phi[j])phi[j]=j;
11                 phi[j]=phi[j]/i*(i-1);
12             }
13 }