python - 计算欧拉函数

Question

我试图找到一种计算欧拉函数的有效方法。

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

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)

score 27 · Accepted Answer

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

因此，如果 n 是一个正整数，则 φ(n) 是 gcd(n, k) = 1 的 1 ≤ k ≤ n 范围内的整数 k 的个数。

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

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

score 5 · Accepted Answer

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

y需要等于n初始值，而不是1
正如一些人在评论中提到的，不要使用整数除法
n % i == 0 is True没有按照您的想法做，因为 Python 链接了比较！即使n % i等于0then 0 == 0is True BUT 0 is True is False！使用括号或只是摆脱比较，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)

score 4 · Accepted Answer

为范围内的每一对计算 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

score 3 · Accepted Answer

其他用户提到的大多数实现都依赖于调用 gcd() 或 isPrime() 函数。如果您要多次使用 phi() 函数，则需要事先计算这些值。一种方法是使用所谓的筛算法。

https://stackoverflow.com/a/18997575/7217653这个关于 stackoverflow 的答案为我们提供了一种快速查找低于给定数字的所有素数的方法。

好的，现在我们可以用数组中的搜索替换 isPrime()。

现在实际的 phi 函数：

维基百科给了我们一个明确的例子：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

换句话说，这就是说 36 的不同质因数是 2 和 3；从 1 到 36 的 36 个整数中有一半能被 2 整除，剩下 18 个；其中三分之一可以被 3 整除，剩下 12 个与 36 互质的数。确实有 12 个正整数与 36 互质且小于 36：1、5、7、11、13、17、19、23 、25、29、31 和 35。

TL;博士

换句话说：我们必须找到我们数字的所有质因数，然后使用 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

score 3 · Accepted Answer

我正在研究 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

score 2 · Accepted Answer

关于效率，我没有注意到有人提到 gcd(k,n)=gcd(nk,n)。使用这个事实可以节省大约一半的涉及使用 gcd 的方法所需的工作。只需从 2 开始计数（因为 1/n 和 (n-1)/k 总是不可约的），每次 gcd 为 1 时加 2。

score 2 · Accepted Answer

看起来您正在尝试使用欧拉的乘积公式，但您没有计算除 a 的素数的数量。您正在计算与 a 相对质数的元素数。

另外，因为 1 和 i 都是整数，所以除法也是，在这种情况下你总是得到 0。

score 2 · Accepted Answer

这是orlp答案的简短实现。

from math import gcd
def phi(n): return sum([gcd(n, k)==1 for k in range(1, n+1)])

正如其他人已经提到的那样，它为性能优化留下了空间。

score 1 · Accepted Answer

实际上要计算 phi（任何数字说 n）
我们使用公式
，其中 p 是 n 的素数。

因此，您的代码中几乎没有错误：
1.y应该等于n
2。因为1/i实际上1两者i都是整数，因此它们的评估也将是整数，因此会导致错误的结果。

这是带有所需更正的代码。

定义 phi(n):
    y = n
    对于范围内的 i (2,n+1)：
        如果 isPrime(i) 和 n % i == 0 ：
            y -= y/i
        别的：
            继续
    返回整数（y）

python - 计算欧拉函数

9 回答 9

Related

Reference