欧拉函数：即求1到正整数n之间与n互质的数的个数。（特别的， 当 n = 1 时， 数目F（n） = 1） 。

        现在分析一下， 当n大于1时的情况， 当 n 为素数时， 很显然 F（n） = n-1 。当n不是素数时，有唯一分解定理可知， n 可以分解成 几个 素数 乘积的形式。例如

 4 = 2 * 2， F(2) = 1;  对于 2^(n+1)  在每一个 F(2^(n+1)) = 2^n * F(2) (想一想为什么？ 例如 F（5） = 4， 这 4 个数分别为 1， 2， 3， 4 。 则， 1+5， 2+5， 3+5， 4+5， 1+（2*5），，，4+（4*5）一定和25互质， 则 F（25） = 5*F（5） = 4*5 = 20)   又因为 欧拉函数是积性函数（这个证明较为繁琐， 在此略去！）

所以， n = a^(i+1)* b^(j+1),,,  则 F（n） = F(a)*a^i  *  F(b)*b^j,,,

 

详见代码：

1 #include
      
        2 #include
       
         3 using namespace std; 4  5 int eular(int n) 6 { 7     int ret = 1, i; 8     for(i=2; i*i<=n; i++) 9         if(n%i==0)10         {11             n/=i, ret*=i-1;12             while(n%i==0)13             n/=i, ret*=i;14         }15         if(n>1)16         ret*=n-1;17         return ret;18 }19 20 int main()21 {22     int n;23     while(scanf("%d", &n)!=EOF)24     {25         n=eular(n);26         printf("%d\n", n);27     }28     return 0;29 }
       
      

 

《2》线性筛选--欧拉函数

1 //线性筛法求解极性函数（欧拉函数） 2 memset(check, false, sizeof(check)); 3 fai[1] = 1; 4 int tot = 0; 5 for(int i=2; i<=N; i++) 6 { 7     if(!check[i]) 8     { 9         prime[tot++] = i;10         fai[i] = i-1;11     }12 for(int j=0; j
      
       N) break;15     check[i*peime[j]] = true;16     if(i%prime[j]==0)17     {18         fai[i*prime[j]] = fai[i]*prime[j];19         break;20     }21     else22     {23         fai[i*prime[j]] = fai[i]*(prime[j]-1);24     }25 }26 }