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

Python如何引用欧拉常数

欧拉常数(Euler-Mascheroniconstant)。

学过高等数学的人都知道，调和级数S=1+1/2+1/3+..是发散的这时引用欧拉常数。

在数论，对正整数n，欧拉函数是小于n的正整数中与n互质的数的数目（因此φ(1)=1）此函数以其首名研究者欧拉命名(Euler’stotientfunction)，它又称为Euler’stotientfunction、φ函数、欧拉商数等例如φ(8)=4，因为1，3，5，7均和8互质。

相关问答

Q1: Python--math库

        Python math 库提供许多对浮点数python写欧拉函数的数学运算函数python写欧拉函数，math模块不支持复数运算python写欧拉函数，若需计算复数python写欧拉函数，可使用cmath模块（本文不赘述）。

使用dir函数python写欧拉函数，查看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)    #伽马函数的自然对数

Q2: 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那么φ

Q3: 欧拉筛法求素数python

# 欧拉筛法求素数

A = [i for i in range(2,10**8+1)]

L = len(A)

for i in range(L):

p = A[i]

if p != 0:

A[i+p:L:p] = [0]*len(A[i+p:L:p])

A = list(filter(lambda x: x != 0,A))

print(len(A))

程序缩进如图所示

Q4: 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)。

具体代码：

#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;

}

Q5: 欧拉计划的例题解答

欧拉计划的第一题是：

列举出10以下所有3或5的倍数，我们得到 3, 5, 6 和 9。他们的和是23。

求1000以下所有3或5的倍数之和。

虽然这题比欧拉计划大多数题目要容易的多，我们仍然可以用它来分析不同解体方法的效率。

用穷举法来测试1000以下的所有自然数，再将它们相加就能得到这题的结果。这很容易实现，用以下两种不同的编程语言都能很快求解出答案。

Python：

print sum(filter(lambda x:x % 3 == 0 or x % 5 == 0, xrange(1, 1000)))

C++：

#include iostream

using namespace std;

int main( ) {

int sum = 0;

for (int i = 0; i 1000; i++)

if ( i % 3 == 0 || i % 5 == 0 )

sum += i;

cout sum endl;

return 0;

}

但如果用排容原理进行求和，就可以减少1000多次运算。

Python 实现：

def sum1toN(n):

return n * (n + 1) / 2

def sumMultiples(limit, a):

return sum1toN((limit - 1) / a) * a

sumMultiples(1000, 3) + sumMultiples(1000, 5) - sumMultiples(1000, 15)

采用这种方法，计算10,000,000以下或1000以下所花费的时间是相等的。若用大O符号来描述两种方法的优劣，那么穷举算法为O(n)而高效的算法为O(1)。

python写欧拉函数的介绍就聊到这里吧，感谢你花时间阅读本站内容，更多关于python欧拉法代码、python写欧拉函数的信息别忘了在本站进行查找喔。