锐客网

  1. 首页 > 睿知 > it技术 > >

欧拉函数c语言原理 欧拉公式的c语言实现

IT技术函数

C语言中这么求欧拉函数的值有什么问题吗，题目如下 。#includestdio.h
int main() {
int sum,x,i,a;
while(scanf("%d", x)!=EOF) {
a=x;
sum=a-1;
while (x2){
x--;
for (i=2; i=x;i++) {
if (a%i == 0x%i == 0) {
sum--;
break;
}
}
}
printf("%d\n", sum);
}
return 0;
}
没问题，结果是对的 。
其中注意，1是和大于1的每个数互质的 。你将sum置为a-1，然后i从2开始计算,刚好把1默认算进去了 。因此结果是正确的 。
C语言实现欧拉函数int eular(int n)
{
int ret=1,i;//定义变量
for(i=2;i*i=n;i++)//从i=2开始循环欧拉函数c语言原理，判定条件为i*i小于等于n欧拉函数c语言原理，循环一次i增加1
if(n%i==0)//判定条件为n除以i的余数等于0
{
n/=i,ret*=i-1;//n=n/i欧拉函数c语言原理，ret = ret*(i-1)
while(n%i==0)//当n除以i的余数等于0时执行下面的语句欧拉函数c语言原理，否则跳过
n/=i,ret*=i;
}
if(n1)//如果n1执行下面语句欧拉函数c语言原理，否则跳过
ret*=n-1;//ret = ret*(n-1)
return ret;
}
直接复制的百度百科的，没具体看是什么功能
2的欧拉函数值为什么是一.欧拉函数
1.算法描述
1～N 中与 N 互质的数的个数被称为欧拉函数，也就是说 ， 1~N中与N的最大公约数是1的数的个数 ， 记作\phi \left ( N \right ) 。
在算术基本定理中 ， 若
N=p_{1}^{\alpha _{1}}p_{2}^{\alpha _{2 }}\cdot \cdot \cdot p_{n}^{\alpha _{n}}
则：
\phi \left ( N \right )=N\left ( 1-\frac{1}{p_{1}} \right )\left ( 1-\frac{1}{p_{2}} \right )\cdot \cdot \cdot \left ( 1-\frac{1}{p_{n}} \right )
证明如下：我们可以分以下几步求出N的互质的数
1.在1~N这些数中 ， 将p1、p2、……pn的倍数剔除，很显然，pi的倍数和N的最大公约数是不是1.
N-\frac{N}{p_{1}}-\frac{N}{p_{2}}-\cdot \cdot \cdot -\frac{N}{p_{n}}
2.但需要注意是，在1~N这些数中 ， pi*pj的倍数倍剔除了两次，因此要把他们加上
\frac{N}{p_{1}p_{2}}+\frac{N}{p_{1}p_{3}}+\cdot \cdot \cdot +\frac{N}{p_{n-1}p_{n}}
3.但是，对于pi*pj*pk的倍数，在第1步时，被剔除了三次，在第2步时，被pi*pj、pi*pk、pj*pk加上了三次，因而我们需要把pi*pj*pk的倍数再剔除一次：
-\frac{N}{p_{1}p_{2}p_{3}}-\frac{N}{p_{1}p_{2}p_{4}}-\cdot \cdot \cdot -\frac{N}{p_{n-2}p_{n-1}p_{n}}
4.那么可以想到，接下来就是所有N除以四项乘积的和，减去N除以五项乘积的和……
事实上，将所有的这些式子加起来，得到的就是
\phi \left ( N \right )=N\left ( 1-\frac{1}{p_{1}} \right )\left ( 1-\frac{1}{p_{2}} \right )\cdot \cdot \cdot \left ( 1-\frac{1}{p_{n}} \right )
首先，当分母为奇数个乘积时，那每一项的符号都是-1的奇数次方，还是-1；当分母为偶数个乘积时 ， 每一项的符号都是-1的偶数次方 ， 为正 。
这个公式可以类比于约数的个数,道理是一样的 。
\left ( p_{1}^{0}+p_{1}^{1} +\cdot \cdot \cdot + p_{1}^{\alpha _{1}}\right )\left ( p_{2}^{0}+p_{2}^{1} +\cdot \cdot \cdot + p_{2}^{\alpha _{2}}\right )\cdot \cdot \cdot \left ( p_{n}^{0}+p_{n}^{1} +\cdot \cdot \cdot + p_{n}^{\alpha _{n}}\right )
2.代码实现
可以发现，欧拉函数并不关心每个质因子的指数是什么，因而我们不用s来存储指数 ， 也不用map来存储质因子，每当我们发现一个质数i时 ， 让结果乘以(1-1/i) 。但需要注意两点：
1.对于(1-1/i) ， 1/i是小数，就这么写的话，那每一项都是1了，所以要×i再÷i，即：res=res/i*(i-1) 。
2.一定要记得在循环结束后，判断x是否会大于1，如果大于1，说明还存在x这个质因子，再执行一步：res=res/x*(x-1) 。

推荐阅读


上一篇：redis有大量timewait连接，redis连接时间和超时时间多少合理

下一篇：角色扮演游戏书屋教案，角色扮演游戏教案设计意图