欧拉函数线性求法
欧拉函数的线性求法运用了欧拉函数的积性，即当gcd(n,m)=1时，有φ(n)*φ(m)=φ(n*m)；于是我们可以运用这一性质得到以下公式。
我们有欧拉函数的通式$\varphi \left( n\right) =n\left( 1-\dfrac {1} {p_{1}}\right) \left( 1-\dfrac {1} {p_{2}}\right) \ldots \left( 1-\dfrac {1} {p_{n}}\right)$
其中p1,p2...pn为n的质因数，唯一分解定理。
1 int euler(int n){ 2 int res=n,a=n; 3 for(int i=2;i*i<=a;i++){ 4 if(a%i==0){ //发现质因数 5 res=res/i*(i-1); //通分即为此 6 while(a%i==0) a/=i; 7 } 8 } 9 if(a>1) res=res/a*(a-1); 10 return res; 11 } 12 13 欧拉函数欧拉函数
我们还可以打表。
1 #define Max 1000001 2 int euler[Max]; 3 void Init(){ 4 euler[1]=1; 5 for(int i=2;i<Max;i++) 6 euler[i]=i; 7 for(int i=2;i<Max;i++) 8 if(euler[i]==i) //i为质数 9 for(int j=i;j<Max;j+=i) 10 euler[j]=euler[j]/i*(i-1); //一方面计算，另一方面表示这个数j不是质数 11 }线性筛欧拉 优质内容筛选与推荐>>
1、LINUX 双网卡绑定
2、python, 操作文件和目录
3、祝大家新年快乐！
4、240. Search a 2D Matrix II
5、用UIPickerView来显示省和市