博客

欧拉函数是数论中的一个重要的函数，也叫做欧拉φ函数（Euler’s totient function）。它表示小于等于正整数n的数中与n互质的数的个数。例如，欧拉函数φ(6)表示小于等于6且与6互质的数的个数，而6与1,5互质，2,3,4不互质，所以φ(6)=2。

欧拉函数的表示式为：φ(n)= n (1-1/p1) * (1-1/p2) … *(1-1/pk)。其中，pi表示n的质因数，k表示n的不同质因数个数。例如，对于n=12，12=2^2 * 3，即n有2个质因数2和3，所以φ(12)=12 * (1-1/2) * (1-1/3) = 4。

在Python中，可以通过以下两种方式计算欧拉函数：

1. 常规暴力算法

首先，我们需要计算n的所有质因数。

def primeFactors(n):
    factors = []
    i = 2
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            if i not in factors:
                factors.append(i)
    if n > 1:
        if n not in factors:
            factors.append(n)
    return factors

然后，我们带入欧拉函数表示式进行计算即可。

def eulerPhi(n):
    factors = primeFactors(n)
    phi = n
    for factor in factors:
        phi *= (1 - 1/factor)
    return int(phi)

1. 线性筛法

线性筛法是一种常用的高效算法，可以在O(n)的时间复杂度内计算出1~n范围内所有整数的欧拉函数。

def eulerPhi(n):
    phi = [i for i in range(n+1)]
    for i in range(2, n+1):
        if phi[i] == i:
            for j in range(i, n+1, i):
                phi[j] = phi[j] // i * (i - 1)
    return phi

其中，phi[i]表示i的欧拉函数。在第二个for循环中，从i开始，以i为间隔遍历1~n范围内的所有数，将它们的欧拉函数进行更新。更新公式为：phi[j] = phi[j] // i * (i – 1)，这里//表示整数除法。

以上就是Python中计算欧拉函数的两种方式。