【算法基础：数学知识】4.3 欧拉函数

**欧拉函数**

欧拉函数（Euler's totient function），又称为欧拉φ函数，是一个重要的数论概念。它定义在正整数集上，表示出某个数与1 到该数之间的所有较小正整数共有的倍数数量。

**定义**

对于任何正整数 n，欧拉函数 φ(n) 定义为：

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

其中，gcd(x,n) 表示 x 和 n 的最大公约数。

**性质**

欧拉函数有以下几个重要的性质：

1. **对称性**：φ(n) = φ(n)。
2. **乘法性质**：如果 a 和 b 是互质的，则 φ(ab) = φ(a)φ(b)。
3. **归纳性质**：对于任何正整数 n，φ(n+1) = φ(n)+n。

**计算欧拉函数**

欧拉函数可以通过以下几种方法来计算：

1. **直接计算法**：直接计算出1 到 n 之间的所有较小正整数与 n 的最大公约数，然后统计出 gcd(x,n)=1 的数量。
2. **质因数分解法**：如果 n 的质因数分解为 p1^a1 * p2^a2 * ... * pk^ak，则 φ(n) = n * (1-1/p1)^a1 * (1-1/p2)^a2 * ... * (1-1/pk)^ak。

**代码示例**

以下是 Python语言下的欧拉函数计算的代码示例：

def euler_function(n):
 """
 计算欧拉函数φ(n)
 Parameters:
 n (int): 正整数 Returns:
 int: 欧拉函数φ(n)的值 """
 result =0 for x in range(1, n+1):
 if gcd(x, n) ==1:
 result +=1 return resultdef gcd(a, b):
 """
 计算 a 和 b 的最大公约数 Parameters:
 a (int): 正整数 b (int): 正整数 Returns:
 int: a 和 b 的最大公约数 """
 while b !=0:
 a, b = b, a % b return a# 测试欧拉函数计算n =10print("φ({}) = {}".format(n, euler_function(n)))