Python 计算 Eulers Totient 函数
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/18114138/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Computing Eulers Totient Function
提问by Brock West
I am trying to find an efficient way to compute Euler's totient function.
我试图找到一种有效的方法来计算欧拉的 totient 函数。
What is wrong with this code? It doesn't seem to be working.
这段代码有什么问题？它似乎不起作用。
def isPrime(a):
return not ( a < 2 or any(a % i == 0 for i in range(2, int(a ** 0.5) + 1)))
def phi(n):
y = 1
for i in range(2,n+1):
if isPrime(i) is True and n % i == 0 is True:
y = y * (1 - 1/i)
else:
continue
return int(y)
回答by orlp
Here's a much faster, working way, based on this description on Wikipedia:
根据维基百科上的描述，这是一种更快的工作方式：
Thus if n is a positive integer, then φ(n) is the number of integers k in the range 1 ≤ k ≤ n for which gcd(n, k) = 1.
因此，如果 n 是一个正整数，则 φ(n) 是 1 ≤ k ≤ n 范围内的整数 k 的数量，其中 gcd(n, k) = 1。
I'm not saying this is the fastest or cleanest, but it works.
我并不是说这是最快或最干净的，但它确实有效。
from math import gcd
def phi(n):
amount = 0
for k in range(1, n + 1):
if gcd(n, k) == 1:
amount += 1
return amount
回答by Joel
It looks like you're trying to use Euler's product formula, but you're not calculating the number of primes which divide a. You're calculating the number of elements relatively prime to a.
看起来您正在尝试使用欧拉的乘积公式，但您没有计算将 a 相除的素数的数量。您正在计算与 a 互质的元素的数量。
In addition, since 1 and i are both integers, so is the division, in this case you always get 0.
此外，由于 1 和 i 都是整数，因此除法也是整数，在这种情况下，您总是会得到 0。
回答by Jared
You have three different problems...
你有三个不同的问题...
yneeds to be equal tonas initial value, not1- As some have mentioned in the comments, don't use integer division
n % i == 0 is Trueisn't doing what you think because of Python chaining the comparisons! Even ifn % iequals0then0 == 0isTrueBUT0 is TrueisFalse! Use parens or just get rid of comparing toTruesince that isn't necessary anyway.
y需要等于n作为初始值，而不是1- 正如一些人在评论中提到的，不要使用整数除法
n % i == 0 is True因为 Python 链接比较，所以没有按照您的想法行事！即使n % i等于0然后0 == 0是TrueBUT0 is True是False！使用括号或只是摆脱比较，True因为无论如何这都没有必要。
Fixing those problems,
解决这些问题，
def phi(n):
y = n
for i in range(2,n+1):
if isPrime(i) and n % i == 0:
y *= 1 - 1.0/i
return int(y)
回答by Bill Bell
With regards to efficiency, I haven't noticed anyone mention that gcd(k,n)=gcd(n-k,n). Using this fact can save roughly half the work needed for the methods involving the use of the gcd. Just start the count with 2 (because 1/n and (n-1)/k will always be irreducible) and add 2 each time the gcd is one.
关于效率，我没有注意到有人提到 gcd(k,n)=gcd(nk,n)。使用这个事实可以节省涉及使用 gcd 的方法所需的大约一半的工作。只需从 2 开始计数（因为 1/n 和 (n-1)/k 总是不可约的）并且每次 gcd 为 1 时加 2。
回答by Serinice
I'm working on a cryptographic library in python and this is what i'm using. gcd()is Euclid's method for calculating greatest common divisor, and phi()is the totient function.
我正在用 python 开发一个加密库，这就是我正在使用的。gcd()是欧几里德计算最大公约数的方法，phi()是totient函数。
def gcd(a, b):
while b:
a, b=b, a%b
return a
def phi(a):
b=a-1
c=0
while b:
if not gcd(a,b)-1:
c+=1
b-=1
return c
回答by alphaguy
Actually to calculate phi(any number say n)
We use the Formula
where p are the prime factors of n.
实际上要计算phi（任何数字，比如n）
我们使用公式
，其中p是n的素数。
So, you have few mistakes in your code:
1.yshould be equal to n
2. For 1/iactually 1and iboth are integers so their evaluation will also be an integer,thus it will lead to wrong results.
所以，你必须在你的代码一些错误：
1y应该等于n
2。对于1/i实际1和i都是整数，所以他们的评价也将是一个整数，从而会导致错误的结果。
Here is the code with required corrections.
这是带有所需更正的代码。
def phi(n):
y = n
for i in range(2,n+1):
if isPrime(i) and n % i == 0 :
y -= y/i
else:
continue
return int(y)
回答by Rodrigo López
Calculating gcd for every pair in range is not efficient and does not scales. You don't need to iterate throught all the range, if n is not a prime you can check for prime factors up to its square root, refer to https://stackoverflow.com/a/5811176/3393095. We must then update phi for every prime by phi = phi*(1 - 1/prime).
为范围内的每一对计算 gcd 效率不高且无法缩放。您不需要遍历所有范围，如果 n 不是素数，您可以检查素数的平方根，请参阅https://stackoverflow.com/a/5811176/3393095。然后我们必须通过 phi = phi*(1 - 1/prime) 为每个素数更新 phi。
def totatives(n):
phi = int(n > 1 and n)
for p in range(2, int(n ** .5) + 1):
if not n % p:
phi -= phi // p
while not n % p:
n //= p
#if n is > 1 it means it is prime
if n > 1: phi -= phi // n
return phi
回答by Timo Strating
Most implementations mentioned by other users rely on calling a gcd() or isPrime() function. In the case you are going to use the phi() function many times, it pays of to calculated these values before hand. A way of doing this is by using a so called sieve algorithm.
其他用户提到的大多数实现都依赖于调用 gcd() 或 isPrime() 函数。如果您要多次使用 phi() 函数，事先计算这些值是值得的。一种方法是使用所谓的筛分算法。
https://stackoverflow.com/a/18997575/7217653This answer on stackoverflow provides us with a fast way of finding all primes below a given number.
https://stackoverflow.com/a/18997575/7217653stackoverflow 上的这个答案为我们提供了一种快速找到给定数字以下所有质数的方法。
Oke, now we can replace isPrime() with a search in our array.
好的，现在我们可以用数组中的搜索替换 isPrime()。
Now the actual phi function:
现在实际的phi函数：
Wikipedia gives us a clear example: https://en.wikipedia.org/wiki/Euler%27s_totient_function#Example
维基百科给了我们一个清晰的例子：https: //en.wikipedia.org/wiki/Euler%27s_totient_function#Example
phi(36) = phi(2^2 * 3^2) = 36 * (1- 1/2) * (1- 1/3) = 30 * 1/2 * 2/3 = 12
In words, this says that the distinct prime factors of 36 are 2 and 3; half of the thirty-six integers from 1 to 36 are divisible by 2, leaving eighteen; a third of those are divisible by 3, leaving twelve numbers that are coprime to 36. And indeed there are twelve positive integers that are coprime with 36 and lower than 36: 1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, and 35.
phi(36) = phi(2^2 * 3^2) = 36 * (1- 1/2) * (1- 1/3) = 30 * 1/2 * 2/3 = 12
换句话说，这表示 36 的不同质因数是 2 和 3；从 1 到 36 的 36 个整数的一半可以被 2 整除，剩下 18 个；其中三分之一可以被 3 整除，剩下十二个与 36 互质的数。 事实上，有十二个与 36 互质且小于 36 的正整数：1, 5, 7, 11, 13, 17, 19, 23 、25、29、31 和 35。
TL;DR
TL; 博士
With other words: We have to find all the prime factors of our number and then multiply these prime factors together using foreach prime_factor: n *= 1 - 1/prime_factor.
换句话说：我们必须找到数字的所有质因数，然后使用 foreach prime_factor 将这些质因数相乘：n *= 1 - 1/prime_factor。
import math
MAX = 10**5
# CREDIT TO https://stackoverflow.com/a/18997575/7217653
def sieve_for_primes_to(n):
size = n//2
sieve = [1]*size
limit = int(n**0.5)
for i in range(1,limit):
if sieve[i]:
val = 2*i+1
tmp = ((size-1) - i)//val
sieve[i+val::val] = [0]*tmp
return [2] + [i*2+1 for i, v in enumerate(sieve) if v and i>0]
PRIMES = sieve_for_primes_to(MAX)
print("Primes generated")
def phi(n):
original_n = n
prime_factors = []
prime_index = 0
while n > 1: # As long as there are more factors to be found
p = PRIMES[prime_index]
if (n % p == 0): # is this prime a factor?
prime_factors.append(p)
while math.ceil(n / p) == math.floor(n / p): # as long as we can devide our current number by this factor and it gives back a integer remove it
n = n // p
prime_index += 1
for v in prime_factors: # Now we have the prime factors, we do the same calculation as wikipedia
original_n *= 1 - (1/v)
return int(original_n)
print(phi(36)) # = phi(2**2 * 3**2) = 36 * (1- 1/2) * (1- 1/3) = 30 * 1/2 * 2/3 = 12
