欧拉函数用符号φ表示，φ(n)表示小于等于n的正整数数中与n互质的数的个数

φ(1)=1  ;  1

φ(2)=1 ;   1

 

φ(3)=2 ;   1,2

φ(4)=2 ;   1,3

φ(5)=5 ;   1,2,3,4

φ(6)=2 ;   1,5  

 

φ(7)=6 ;    1,2,3,4,5,6

φ(8)=4 ;   1,3,5,7

…………………………

其中当n为素数时，φ(n)=n-1;   然后再将这个问题推广到一般性——1.怎么求任意的φ(n)。2.怎么求n以内所有的φ(n)

 

1.对于任意的n，φ(n)=n x (1-p1) x (1-p2) x (1-p3) …………(1-pm)

其中p1,p2,p3……pm是n能分解出来的素因子。为了编程实现，只需要将该公式简单变形

φ(n)=n x [(p1-1)/p1] x [(p2-1)/p2] x [(p3-1)/p3] …………[(pm-1)/pm]

用文字来描述就是 “找到每一个n能分解出来的素因子pi，然后除以pi再乘以(pi-1)”

#include 
     
      #include 
      
       int main(){    int n,m,ans;    while(scanf("%d",&n)!=EOF && n)    {        ans=n;        m=(int)sqrt(n+0.5);        for(int i=2; i<=m; i++)  //枚举因子            if(!(n%i))  //可分解出这个因子            {                ans=ans/i*(i-1);                while(!(n%i)) n/=i;  //除干净这个因子            }        if(n>1)  ans=ans/n*(n-1);  //剩下的这个n一定是一个素数,其实就是最后一个素因子        printf("%d\n",ans);    }    return 0;}
      
     

 

2.有时候我们需要知道n以内所有数字的欧拉函数，那么一个直观的方法就是对这n个数一次运行上面的代码就额可以求出，但是这不是最好的方法，最好的方法是筛法，和筛素数无论是思想还是代码上都很像

我们知道要求一个数n的φ(n)是要找出它所包含的所有的素因子的，那么我们可以用一种逆思维，先枚举所有的素数，然后看哪些数字的因子中包含这个素数，然后我们再“除以这个素数p再乘以(p-1)”

#include 
     
      #include 
      
       #include 
       
        #define N 10000010int phi[N];int main(){    int n=100000;  //算出100000以内所有数字的欧拉函数值    memset(phi,0,sizeof(phi));    phi[1]=1;    for(int i=2; i<=n; i++) if(!phi[i])  //i是一个素因子        for(int j=i; j<=n; j+=i)  //j表示i的倍数        {            if(!phi[j])  phi[j]=j;            phi[j]=phi[j]/i*(i-1);        }/*    for(int i=1; i<=10; i++)        printf("%d %d\n",i,phi[i]);*/    return 0;}