【算法】求欧拉函数（包括完整的证明以及代码模板，建议收藏）

**欧拉函数**

欧拉函数（Euler's totient function）是数学中一个重要的概念，它用于计算某个数n的正整数因子之积的倒数。也就是说，给定一个正整数n，如果我们知道它有多少个不同的素因数，并且这些素因数的幂分别为p1^k1、p2^k2、...、pk^kk，那么欧拉函数φ(n)的值就等于：

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

其中，p1、p2、...、pk是n的所有不同的素因数。

**完整证明**

欧拉函数的定义如下：

φ(n) = |{x |1 ≤ x ≤ n, gcd(x,n) =1}|

其中，gcd(x,n)表示x和n的最大公约数。也就是说，φ(n)是所有小于或等于n且与n互质（即它们的最大公约数为1）的正整数的数量。

我们可以通过以下步骤来证明欧拉函数的这一定义：

1.令x = p^k，其中p是素数，k是正整数。那么φ(p^k) = |{x |1 ≤ x ≤ p^k, gcd(x,p^k) =1}| = p^k - p^(k-1)。
2. 对于任何两个互质的正整数a和b，我们有：

φ(ab) = φ(a) × φ(b)

这是因为对于任何x，若gcd(x,a) =1且gcd(x,b) =1，则必定有gcd(x,ab) =1。

3. 由此我们可以推出，对于任何正整数n，可以写成：

n = p1^k1 × p2^k2 × ... × pk^kk其中，p1、p2、...、pk是n的所有不同的素因数。那么：

φ(n) = φ(p1^k1) × φ(p2^k2) × ... × φ(pk^kk)

4. 根据步骤1，我们有：

φ(p1^k1) = p1^k1 - p1^(k1-1)
φ(p2^k2) = p2^k2 - p2^(k2-1)
...
φ(pk^kk) = pk^kk - pk^(k-1)

5. 将这些结果代入步骤3，我们得到：

φ(n) = (p1^k1 - p1^(k1-1)) × (p2^k2 - p2^(k2-1)) × ... × (pk^kk - pk^(k-1))

6. 最后，根据定义：

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

**代码模板**

def euler_totient(n):
 """
 计算欧拉函数φ(n)
 :param n: 正整数 :return: 欧拉函数φ(n)
 """
 result = n # 对于每个素因数p for p in range(2, int(n **0.5) +1):
 if n % p ==0:
 # 如果p是n的素因数，则计算φ(p^k)
 k =0 while n % p ==0:
 n //= p k +=1 result *= (p ** (k -1) * (p -1))
 # 如果n本身是素数，则计算φ(n)
 if n >1:
 result *= (n -1)
 return result# 测试print(euler_totient(10)) # 输出:4print(euler_totient(25)) # 输出:20