计算Eulers-tolient函数

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

我正在用python开发一个密码库，这就是我正在使用的。gcd()是欧几里德计算最大公约数的方法，而phi()是总函数。

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

Answer 2

你有三个不同的问题。。。

1. y需要等于n作为初始值，而不是1
2. 正如评论中提到的，不要使用整数除法
3. n % i == 0 is True没有做你认为的事情，因为Python链接了比较！即使n % i等于0，那么0 == 0是True但是0 is True是False！使用parens或者去掉与True的比较，因为这是不必要的。

解决这些问题

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)

Answer 3

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

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