两种欧拉函数模板

求欧拉函数代码的方式：直接求和打表
欧拉函数的作用：一个数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;
	}

  
 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
 

其中，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); } }
 }

  
 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
 

如果对后端、爬虫、数据结构算法等感性趣欢迎关注我的个人公众号交流：bigsai

文章来源: bigsai.blog.csdn.net，作者：Big sai，版权归原作者所有，如需转载，请联系作者。

原文链接：bigsai.blog.csdn.net/article/details/84887939