python - 计算欧拉的 Totient 函数

Question

我正试图找到一种有效的方法来计算 Euler's totient function .

这段代码有什么问题？它似乎不起作用。

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)

Answer 1

根据维基百科上的描述，这里有一个更快的工作方式:

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.

我并不是说这是最快或最干净的，但它确实有效。

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