欧拉函数详解（C语言实现欧拉函数的完整教程）

欧拉函数的数学性质

欧拉函数有几个重要性质，可以帮助我们高效计算：

1. 如果 p 是质数，则 φ(p) = p - 1。
2. 如果 p 是质数，k 是正整数，则 φ(p^k) = p^k - p^{k-1}。
3. 如果 m 和 n 互质，则 φ(m × n) = φ(m) × φ(n)。（积性函数）

基于这些性质，我们可以利用质因数分解来快速计算 φ(n)。

C语言实现欧拉函数

下面我们提供两种实现方式：一种是基础暴力法（适合理解），另一种是基于质因数分解的高效算法。

方法一：暴力法（适合初学者理解）

思路：遍历 1 到 n，对每个数计算 gcd(i, n)，若为 1 则计数加一。

#include <stdio.h>// 计算最大公约数（欧几里得算法）int gcd(int a, int b) {    while (b != 0) {        int temp = b;        b = a % b;        a = temp;    }    return a;}// 暴力法计算欧拉函数int euler_phi_brute(int n) {    if (n == 1) return 1;    int count = 0;    for (int i = 1; i <= n; i++) {        if (gcd(i, n) == 1) {            count++;        }    }    return count;}int main() {    int n = 9;    printf("φ(%d) = %d\n", n, euler_phi_brute(n));    return 0;}

这种方法时间复杂度为 O(n log n)，当 n 很大时效率较低，但逻辑清晰，适合学习理解。

方法二：基于质因数分解的高效算法

利用公式：
φ(n) = n × ∏(1 - 1/p)，其中 p 是 n 的所有不同质因数。

例如：n = 12 = 2² × 3
φ(12) = 12 × (1 - 1/2) × (1 - 1/3) = 12 × 1/2 × 2/3 = 4

#include <stdio.h>// 高效计算欧拉函数int euler_phi(int n) {    int result = n; // 初始化为 n    // 从 2 开始尝试所有可能的质因数    for (int p = 2; p * p <= n; p++) {        // 如果 p 是 n 的质因数        if (n % p == 0) {            // 去除所有 p 因子            while (n % p == 0) {                n /= p;            }            // 应用公式：result = result * (1 - 1/p)            result -= result / p;        }    }    // 如果 n 还大于 1，说明它本身是一个质数    if (n > 1) {        result -= result / n;    }    return result;}int main() {    int n = 12;    printf("φ(%d) = %d\n", n, euler_phi(n));    return 0;}

这种方法的时间复杂度为 O(√n)，效率高得多，是实际应用中的推荐做法。

总结

通过本教程，你已经学会了：

• 什么是欧拉函数及其数学意义
• 如何用 C 语言暴力实现欧拉函数
• 如何用高效的质因数分解方法实现C语言实现欧拉函数
• 理解了该数论算法在实际中的价值

无论你是准备算法竞赛，还是学习密码学基础，掌握欧拉函数都是必不可少的一步。希望这篇编程入门教程能帮助你打下坚实的基础！

提示：你可以尝试修改代码，输入不同的 n 值，观察输出结果是否符合预期。