python 实现eulers totient欧拉方程算法

eulers totient欧拉方程算法介绍

欧拉函数（Euler’s Totient Function），通常表示为 𝜑(𝑛)，是一个与正整数 𝑛相关的函数，它表示小于或等于 𝑛的正整数中与 𝑛 互质的数的数目。欧拉函数在数论和密码学中有广泛的应用。

欧拉函数的性质
1.**对于质数 𝑝，有 $\phi (p)=p-1^{\ast \ast }$。
2.**如果 𝑛是质数 𝑝 的 𝑘 次幂，即 $n=p^k$，则 $\phi (n)=p^k-p^{k-1}=p^{k-1}(p-1)\ast \ast$。
3.**如果 𝑚和 𝑛是互质的，则 $\phi (mn)=\phi (m)\phi (n{)}^{\ast \ast }$。
欧拉函数的计算
基于上述性质，我们可以设计一个算法来计算任意正整数 𝑛 的欧拉函数 𝜑(𝑛)。

算法步骤
质因数分解：首先，将 𝑛分解为质因数的乘积形式，即 $n=p_1^{e1}\cdot p_2^{e2}\cdots p_k^{ek}$。
应用欧拉函数的性质：根据性质 2，对于每个质因数 $p_i$，有 $\phi (p_i^{ei})=p_i^{ei-1}(p_i-1)$。
利用性质 3：由于 $p_1,p_2,\dots ,p_k$是互质的，所以 $\phi (n)=\phi (p_1^{e1})\cdot \phi (p_2^{e2})\cdots \phi (p_k^{ek})$。
Python 实现

def euler_phi(n):
    phi = n
    # 遍历从2到sqrt(n)的所有数
    for i in range(2, int(n**0.5) + 1):
        if n % i == 0:
            # 根据性质更新phi
            phi = phi // i * (i - 1)
            # 如果i是n的因子，那么n//i也是n的因子，除非它们是同一个数
            while n % i == 0:
                n //= i
        # 如果n此时已经是质数，则直接返回phi*(n-1)
        if n == 1:
            break
    # 如果n此时大于1，说明n是质数
    if n > 1:
        phi = phi // n * (n - 1)
    return phi

# 测试
print(euler_phi(10))  # 输出 4
print(euler_phi(20))  # 输出 8

这个算法首先尝试找到 𝑛的所有质因数，并应用欧拉函数的性质来逐步计算 𝜑(𝑛)。注意，在遍历过程中，如果 𝑛 能被 𝑖整除，我们就更新 𝑛 和 𝜑(𝑛)，直到 𝑛变为 1 或 𝑖超出 𝑛的平方根。如果最后 𝑛 大于 1，说明 𝑛 是一个质数，我们还需要再应用一次性质 1 来更新 𝜑(𝑛)。

eulers totient欧拉方程算法python实现样例

欧拉函数（Euler’s totient function）是一个数论函数，表示小于等于n的正整数中与n互质的数的个数。可以通过欧拉函数来求解模数为n的群的个数。

欧拉函数的计算公式为：

φ(n) = n * (1 - 1/p1) * (1 - 1/p2) * ... * (1 - 1/pk)

其中p1, p2, …, pk 是 n 的所有质因数。

下面是一个用 Python 实现欧拉函数的算法：

def euler_totient(n):
    phi = n
    p = 2
    while p * p <= n:
        if n % p == 0:
            while n % p == 0:
                n //= p
            phi -= phi // p
        p += 1
    if n > 1:
        phi -= phi // n
    return phi

这个算法的时间复杂度是 O(sqrt(n))，其中 n 是给定的数。

使用示例：

n = 10
result = euler_totient(n)
print(f"φ({n}) = {result}")

输出结果为：

φ(10) = 4

这表示小于等于 10 的正整数中与 10 互质的数的个数为 4。