欧拉函数

View Code

 1 #include<stdio.h>
 2 int Eular(int  n)
 3 {
 4      int i;
 5      int  ans=n;
 6      for(i=2;i*i<=n;++i)
 7      {
 8           if(n%i==0)      //如果i和n不互质，i的倍数全都与n不互质
 9           {
10                 ans-=ans/i;     //排除掉i的倍数
11                 while(n%i==0)
12 n=n/i;       //去掉n中含有的所有i因子
13                 if(n==1)          // n=1 所有因子排除完毕
14 break;
15           }
16   
17      }
18      if(n!=1)        //n！=1  此时的n为素数
19  ans-=ans/n;
20      return ans;
21 }
22 main()
23 {
24      int m;
25      while(scanf("%d",&m)!=EOF,m)
26         printf("%d\n",Eular(m));
27 }

View Code

 1 int Eular(int  n)
 2 {
 3      int i;
 4      int  ans=n;
 5      for(i=2;i*i<=n;++i)
 6      {
 7           if(n%i==0)      //如果i和n不互质，i的倍数全都与n不互质
 8           {
 9                 ans-=ans/i;     //排除掉i的倍数
10                 while(n%i==0)
11                     n=n/i;       //去掉n中含有的所有i因子
12                 if(n==1)          // n=1 所有因子排除完毕
13                     break;
14           }
15           
16      }
17      if(n!=1)        //n！=1  此时的n为素数
18          ans-=ans/n;
19      return ans;
20 }

1、以基数1为递增的欧拉函数值，将目标初始化，处理不能被2和3的数。
2、当以底数为2，基数2（即能被2整除的数）为递增的欧拉函数值。因为将i，以基数2分成i/2段可知，每一段的数从段的开始到段的结束前一个都是互质数。最后一段等于前面所有段的和。
3、当以底数为3，基数2，为递增的欧拉函数值，即处理的是能被3整除的数。
    3-1、判断是否没被第二种处理
           3-1-1、如果被第二种情况处理的就不能做底数。
           3-1-2、如果未被第二种处理则以此时的情况作底数，以保证，前面每一段里的互质数也能够和后面的数互质。此时，i被分为i/3段，每一段进行整理，以i值做基数进行划分处理，此时i值为phi[i]了，所以可以求得phi[i]可以分为phi[i]/i段，然后每一段有i-1个数是满足互质的。那么总的数和就为phi[i]/i*(i-1)
可得算法：
for(i=0;i<=maxn;i++)
     phi[i]=i;
    for(i=2;i<=maxn;i+=2)
      phi[i]/=2;
     for(i=3;i<=maxn;i+=2)
       if(phi[i]==i)
         for(j=i;j<maxn;j+=i)
             phi[j]=phi[j]/i*(i-1);