锐客网

  1. 首页 > 生活百科 > it技术 > >

python求欧拉函数 python欧拉法代码

IT技术欧拉

求欧拉函数的计算公式它于1640年由Descartes首先给出证明，后来Euler(欧拉)于1752年又独立地给出证明，我们称其为欧拉定理 ， 在国外也有人称其为Descartes定理，R V-E=2就是欧拉公式 。
在任何一个规则球面地图上，用R记区域个数 ， V记顶点个数，E记边界个数 ， 则R V-E=2，这就是欧拉定理 。
当R=2时 。
由说明1这两个区域可想象为以赤道为边界的两个半球面，赤道上有两个“顶点”将赤道分成两条“边界” 。
即R=2，V=2，E=2于是R V-E=2,欧拉定理成立 。
Python--math库Python math 库提供许多对浮点数的数学运算函数，math模块不支持复数运算，若需计算复数，可使用cmath模块（本文不赘述） 。
使用dir函数 ， 查看math库中包含的所有内容：
1） math.pi# 圆周率π
2） math.e#自然对数底数
3） math.inf#正无穷大∞，-math.inf#负无穷大-∞
4） math.nan#非浮点数标记，NaN（not a number）
1） math.fabs(x)#表示X值的绝对值
2） math.fmod(x,y)#表示x/y的余数 ， 结果为浮点数
3） math.fsum([x,y,z])#对括号内每个元素求和，其值为浮点数
4） math.ceil(x)#向上取整，返回不小于x的最小整数
5）math.floor(x)#向下取整 ， 返回不大于x的最大整数
6） math.factorial(x)#表示X的阶乘，其中X值必须为整型，否则报错
7） math.gcd(a,b)#表示a,b的最大公约数
8）math.frexp(x)#x = i *2^j，返回（i，j）
9） math.ldexp(x,i)#返回x*2^i的运算值，为math.frexp(x)函数的反运算
10） math.modf(x)#表示x的小数和整数部分
11） math.trunc(x)#表示x值的整数部分
12） math.copysign(x,y)#表示用数值y的正负号，替换x值的正负号
13） math.isclose(a,b,rel_tol =x,abs_tol = y)#表示a，b的相似性，真值返回True，否则False；rel_tol是相对公差：表示a ， b之间允许的最大差值，abs_tol是最小绝对公差，对比较接近于0有用，abs_tol必须至少为0 。
14） math.isfinite(x)#表示当x不为无穷大时，返回True，否则返回False
15） math.isinf(x)#当x为±∞时 ， 返回True，否则返回False
16） math.isnan(x)#当x是NaN，返回True，否则返回False
1） math.pow(x,y)#表示x的y次幂
2） math.exp(x)#表示e的x次幂
3） math.expm1(x)#表示e的x次幂减1
4） math.sqrt(x)#表示x的平方根
5） math.log（x,base）#表示x的对数值，仅输入x值时，表示ln(x)函数
6） math.log1p(x)#表示1 x的自然对数值
7） math.log2(x)#表示以2为底的x对数值
8） math.log10(x)#表示以10为底的x的对数值
1） math.degrees(x)#表示弧度值转角度值
2） math.radians(x)#表示角度值转弧度值
3） math.hypot(x,y)#表示(x,y)坐标到原点(0,0)的距离
4） math.sin(x)#表示x的正弦函数值
5） math.cos(x)#表示x的余弦函数值
6） math.tan(x)#表示x的正切函数值
7）math.asin(x)#表示x的反正弦函数值
8） math.acos(x)#表示x的反余弦函数值
9） math.atan(x)#表示x的反正切函数值
10） math.atan2(y,x)#表示y/x的反正切函数值
11） math.sinh(x)#表示x的双曲正弦函数值
12） math.cosh(x)#表示x的双曲余弦函数值
13） math.tanh(x)#表示x的双曲正切函数值
14） math.asinh(x)#表示x的反双曲正弦函数值
15） math.acosh(x)#表示x的反双曲余弦函数值
16） math.atanh(x)#表示x的反双曲正切函数值
1）math.erf(x)#高斯误差函数
2） math.erfc(x)#余补高斯误差函数
3） math.gamma(x)#伽马函数（欧拉第二积分函数）
4） math.lgamma(x)#伽马函数的自然对数
python的math库有没有欧拉函数？对正整数n ， 欧拉函数是小于n的正整数中与n互质的数的数目（因此φ(1)=1） 。此函数以其首名研究者欧拉命名(Euler’s totient function)，它又称为Euler’s totient function、φ函数、欧拉商数等 。cs-dn 例如φ(8)=4，因为1,3,5,7均和8互质 。
欧拉函数证明E(x)表示比x小的且与x互质的正整数的个数 。
*若p是素数python求欧拉函数 ， E(p)=p-1 。
*E(p^k)=p^k-p^(k-1)=(p-1)*P^(k-1)
证：令n=p^k,小于n的正整数数共有n-1即(p^k-1)个,其中与p不质的数共[p^(k-1)-1]个(分别为1*p,2*p,3*p...p(p^(k-1)-1)) 。
所以E(p^k)=(p^k-1)-(p^(k-1)-1)=p^k-p^(k-1).得证 。
*若ab互质python求欧拉函数，则E(a*b)=E(a)*E(b)，欧拉函数是积性函数.
*对任意数n都可以唯一分解成n=p1^a1*p2^a2*p3^a3*...*pn^an(pi为素数).
则E(n)=E(p1^a1)*E(p2^a2)*E(p3^a3)*...*E(pn^an)
=(p1-1)*p1^(a1-1)*(p2-1)*p2^(a2-1)*...*(pn-1)*pn^(an-1)
=(p1^a1*p2^a2*p3^a3*...*pn^an)*[(p1-1)*(p2-1)*(p3-1)*...*(pn-1)]/(p1*p2*p3*...*pn)
=n*(1-1/p1)*(1-1/p2)*...*(1-1/pn)
* E(p^k)=(p-1)*p^(k-1)=(p-1)*p^(k-2)*p
E(p^(k-1))=(p-1)*p^(k-2)
-当k1时，E(p^k)=E(p*p^(k-1))=E(p^(k-1))*p.
(当k=1时，E(p)=p-1.)
由上式: 设P是素数，
若p是x的约数，则E(x*p)=E(x)*p.
若p不是x的约数，则E(x*p)=E(x)*E(p)=E(x)*(p-1).
*快速求欧拉函数方法：
首先来回顾一下线性筛选素数方法：
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 \cdotp_{1}^{\alpha _{1}}\right )\left ( p_{2}^{0} p_{2}^{1}\cdot \cdot \cdotp_{2}^{\alpha _{2}}\right )\cdot \cdot \cdot \left ( p_{n}^{0} p_{n}^{1}\cdot \cdot \cdotp_{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) 。
具体代码：
#includeiostream
using namespace std;
int n;
int main(){
cinn;
while(n--){
int x;
cinx;
int res=x;
for(int i=2;i=x/i;i){
if(x%i==0){
while(x%i==0){
x=x/i;//i是我的一个质数
}
res=res/i*(i-1);
}
}
if(x1) res=res/x*(x-1);//注意
coutresendl;
}
}
二.筛法求欧拉函数
1.算法描述
第一部分中的算法适合于求单个给定数字对应的欧拉函数的值，但是当题目要求求1~N所有数字的欧拉值之和时，用第一部分中的算法就会花费很多时间，下介绍用筛法求欧拉函数：
首先我们回顾筛法求质数的过程，对于给定的正整数N：
for(int i=2;i=n;i){
if(!str[i]){
primes[cnt]=i;
}
else{
for(int j=0;primes[j]=n/i;j){
str[i*primes[j]]=true;
if(i%primes[j]==0) break;
}
}
}
通过筛法，所有的质数，合数我们都可以遍历到，把所有的质数加入数组primes中，并且str[i*primes[j]]保证了每一个数都会被它的最小质因子筛掉 ， 而if(i%primes[j]==0)保证了不会被重复标记，详细介绍可以参考：
那如何做出修改让筛法求欧拉函数？
1.首先，对于质数i，那么1~i-1都与i互质，那么\phi \left (i \right )=i-1
2.对于合数，即我用str[i*primes[j]]将一个合数筛掉时，我必须同时把它的欧拉值求出来，我们分为以下两种情况：
A.若i可以整除primes[j]，那么primes[j]*i和i有共同的质因子，这是因为primes[j]是i的质因子，那么\phi \left ( i \right )已经包括了1-\frac{1}{primes[j]}这一项，而欧拉函数的值与指数无关，因而：
\phi \left ( i*primes[j] \right )=primes[j]*\phi \left ( i \right )
B.若i不能够整除primes[j]，那么primes[j]*i比i多一个质因子primes[j]，这是因为i本身不包含质因子primes[j]，而primes[j]本身是质数 ， 不会再有质因子，因而：
\phi \left ( i*primes[j] \right )=primes[j]\left ( 1-\frac{1}{primes[j]} \right )\phi \left ( i\right )=\left ( primes[j] -1\right )\phi \left ( i \right )
因而，每一个数的欧拉值都可以通过该种方法求出来 。
2.代码实现
关于代码实现需要注意的是，res的值可能会很大，所以要定义成long long类型 。
具体代码：
#includeiostream
using namespace std;
int x;
const int N=1000010;
long long res;//最后的欧拉函数的值的和，有可能会非常大，要用long long
bool str[N];//是否被标记过
int primes[N];//存放质因子
int cnt;
int phi[N];//各个N的函数值
int main(){
phi[1]=1;//1的欧拉值为1捏
cinx;
for(int i=2;i=x;i){
if(!str[i]){//如果没有被标记过，那么是质数
phi[i]=i-1;//质数的欧拉值就是i-1
primes[cnt]=i;
}
for(int j=0;primes[j]=x/i;j){
str[i*primes[j]]=true;//首先我一定能把所有的合数遍历到，这是肯定的
if(i%primes[j]==0){
//如果i可以整除primes[j]的话,那么i和primes[j]*i的最小质因子是相同的
phi[i*primes[j]]=primes[j]*phi[i];
break;
}
else{
//如果i不可整除primes[j]的话，那么i和primes[j]*i就相差一个primes[j]这个最小质因子
phi[i*primes[j]]=primes[j]*phi[i]*(primes[j]-1)/primes[j];
//那这样就把所有数的欧拉值都存在phi中
}
}
}
for(int i=1;i=x;i){
res=res phi[i];
}
coutres;
}
python怎么调用欧拉距离的函数φ函数python求欧拉函数的值 通式python求欧拉函数：φ(x)=x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…..(1-1/pn),其中p1, p2……pn为xpython求欧拉函数的所有质因数python求欧拉函数，x是不为0的整数 。φ(1)=1（唯一和1互质的数(小于等于1)就是1本身） 。(注意：每种质因数只一个 。比如12=2*2*3那么φ
【python求欧拉函数 python欧拉法代码】关于python求欧拉函数和python欧拉法代码的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站 。

    推荐阅读


    上一篇：华为的鸿蒙系统到底怎样，华为的鸿蒙系统到底有多厉害

    下一篇：抖音直播爬虫，抖音直播爬虫采集