欧拉函数
定义
欧拉函数（Euler's totient function），即
比如说
当 n 是质数的时候，显然有
性质
-
欧拉函数是积性函数。
积性是什么意思呢？如果有
特别地，当
-
-
若
-
由唯一分解定理，设
-
引理：设
证明：显然对于从 1 到
接下来我们证明
-
实现
如果只要求一个数的欧拉函数值，那么直接根据定义质因数分解的同时求就好了。这个过程可以用 Pollard Rho 算法优化。
=== "C++"
```cpp
int euler_phi(int n) {
int m = int(sqrt(n + 0.5));
int ans = n;
for (int i = 2; i <= m; i++)
if (n % i == 0) {
ans = ans / i * (i - 1);
while (n % i == 0) n /= i;
}
if (n > 1) ans = ans / n * (n - 1);
return ans;
}
```=== "Python"
```python
def euler_phi(n):
m = int(sqrt(n + 0.5))
ans = n
for i in range(2, m + 1):
if n % i == 0:
ans = ans // i * (i - 1)
while n % i == 0:
n = n // i
if n > 1:
ans = ans // n * (n - 1)
return ans
```注：如果将上面的程序改成如下形式，会提升一点效率：
=== "C++"
```cpp
int euler_phi(int n) {
int ans = n;
for (int i = 2; i * i <= n; i++)
if (n % i == 0) {
ans = ans / i * (i - 1);
while (n % i == 0) n /= i;
}
if (n > 1) ans = ans / n * (n - 1);
return ans;
}
```=== "Python"
```python
def euler_phi(n):
ans = n
for i in range(2, int(sqrt(n)) + 1):
if n % i == 0:
ans = ans // i * (i - 1)
while n % i == 0:
n = n / i
if n > 1:
ans = ans // n * (n - 1)
return ans
```如果是多个数的欧拉函数值，可以利用后面会提到的线性筛法来求得。 详见：筛法求欧拉函数
欧拉定理
与欧拉函数紧密相关的一个定理就是欧拉定理。其描述如下：
若
扩展欧拉定理
当然也有扩展欧拉定理
证明和 习题 详见 欧拉定理
贡献者：@Menci@queenwen@WenzelTian@CCXXXI@segment-tree@nalemy@Great-designer
本页面最近更新：2/3/2023, 12:00:00 AM，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用