两种欧拉函数模板

求欧拉函数代码的方式：直接求和打表

欧拉函数的作用：一个数n，求小于n的互质的个数。特例：1——oula（1）=1；

欧拉函数的公式：

其中i为x所有质因数。注意：每种质因数只一个

为什么会这样？首先，互质的两个数一定不能有公共因数。比如9和7互质，9和12不互质，因为有共同因数3.

那么我难道需要一个个循环比较吗？

答案先然不可能，因为如果数值过大这是个很大的复杂度。那么我该如何处理？

换一种思维。比如求24中的互质个数。答案是1，5，7，11，13，17，19，23。共8个

1. 24=2 * 2 * 2 * 3；那么在小于12中的数的核心共同质数为2的倍数或者三的倍数。有人可能说明明还要4，6的倍数，那是因为这些倍数囊括在2，3之中。所以我们每个质因数只记录一个。

2. 看在24中，有1/2的是2的倍数，也就是1/2的数是和24有共同因数2.那么就有（1-1/2）的数和24没有共同因数2；

3. 同理那么就有1/3的数和24有共同因数3，并且（1-1/3）=2/3的数没有共同因数3.那么没有因数2和因数三剩下的不就是和24互质么，那么概率=（1-1/2）* （1-1/3）=1/3.总个数为24*1/3=8满足要求。

4. 如果一个因数出现多次怎么排除呢。或者怎么防止4，6这些数被计入因数中，这就要用到质因数分解的思想。只不过我们不需要这个幂出现的次数，只需要让剩余的不可能在存在当前这个数为因数的可能性。

附上直接求代码：

  private static int oula(int team) {
    int i=0;int res=team;int team1=team;
    for(i=2;i<(int)Math.sqrt(team1) 1;i )
    {
      if(team%i==0) {
        res=res/i*(i-1);
        while(team%i==0) {team/=i;}//保证没有i作为因子      
      }
    }
    if(team>1)res=res/team*(team-1);//说明后面还有一个比较大的互质因数大小为team
    return res;
  }

其中，res为结果，team1作为求因数用。如果实在不能理解，好好看下质因数分解。

打表代码：

 int a[]=new int[1000001];
 for(int i=1;i<1000001;i )
 {
   a[i]=i;
 }
 for(int i=2;i 2<1000001;i =2)
 {
   a[i]/=2;
 }
 for(int i=3;i 2<1000001;i =2)
 {
   if(a[i]==i)
   {
     for(int j=i;j i<=1000001;j =i)
     {
       a[j]=a[j]/i*(i-1);
     }
   }
 }