欧拉函数详解（C++语言实现与优化指南）

什么是欧拉函数？

欧拉函数 φ(n) 定义为：对于正整数 n，φ(n) 表示在区间 [1, n] 中与 n 互质（即最大公约数为 1）的整数个数。

例如：

• φ(1) = 1（因为 gcd(1,1)=1）
• φ(6) = 2（因为 1 和 5 与 6 互质）
• φ(9) = 6（因为 1,2,4,5,7,8 与 9 互质）

基础方法：暴力枚举

最直观的方法是遍历 1 到 n 的每个数，用 __gcd 函数（C++ STL 提供）判断是否互质。

#include <iostream>#include <algorithm> // __gcd 在 C++17 前可用，C++17 后用 std::gcdusing namespace std;int euler_phi_basic(int n) {    int count = 0;    for (int i = 1; i <= n; ++i) {        if (__gcd(i, n) == 1) {            count++;        }    }    return count;}int main() {    int n = 9;    cout << "φ(" << n << ") = " << euler_phi_basic(n) << endl;    return 0;}

这种方法时间复杂度为 O(n log n)，当 n 很大时（比如 10⁶ 以上），效率很低。因此我们需要更高效的欧拉函数优化方法。

高效方法：利用欧拉函数公式

欧拉函数有一个重要性质：

若 n 的质因数分解为：n = p₁^k₁ × p₂^k₂ × … × pₘ^kₘ，
则 φ(n) = n × (1 - 1/p₁) × (1 - 1/p₂) × … × (1 - 1/pₘ)

基于此，我们只需找出 n 的所有不同质因数，然后套用公式即可。

#include <iostream>using namespace std;int euler_phi_optimized(int n) {    int result = n;    // 遍历可能的质因数    for (int p = 2; p * p <= n; ++p) {        if (n % p == 0) {            // p 是 n 的一个质因数            while (n % p == 0) {                n /= p; // 移除所有 p 因子            }            result -= result / p; // 等价于 result *= (1 - 1/p)        }    }    // 如果 n 还大于 1，说明它本身是一个质数    if (n > 1) {        result -= result / n;    }    return result;}int main() {    int n = 9;    cout << "φ(" << n << ") = " << euler_phi_optimized(n) << endl;    return 0;}

这个算法的时间复杂度为 O(√n)，比暴力法快得多，适用于大多数编程竞赛和工程场景。

进一步优化：线性筛预处理（批量计算）

如果你需要计算 1 到 N 所有数的欧拉函数值（比如 N = 10⁶），可以使用线性筛法（埃氏筛或欧拉筛）预处理，时间复杂度为 O(N)。

#include <iostream>#include <vector>using namespace std;vector<int> euler_phi_sieve(int N) {    vector<int> phi(N + 1);    vector<bool> is_prime(N + 1, true);    vector<int> primes;    for (int i = 1; i <= N; ++i)        phi[i] = i;    is_prime[0] = is_prime[1] = false;    for (int i = 2; i <= N; ++i) {        if (is_prime[i]) {            primes.push_back(i);            phi[i] = i - 1; // 质数的 φ 值为 i-1        }        for (int p : primes) {            if (i * p > N) break;            is_prime[i * p] = false;            if (i % p == 0) {                phi[i * p] = phi[i] * p;                break;            } else {                phi[i * p] = phi[i] * phi[p];            }        }    }    return phi;}int main() {    int N = 10;    auto phi = euler_phi_sieve(N);    for (int i = 1; i <= N; ++i) {        cout << "φ(" << i << ") = " << phi[i] << endl;    }    return 0;}

总结

通过本教程，你已经掌握了三种 C++语言实现欧拉函数 的方法：

1. 暴力法（适合小数据）
2. 公式法（单次查询高效）
3. 线性筛法（批量预处理）

无论你是学习数论算法的新手，还是准备算法竞赛的选手，理解并掌握欧拉函数优化技巧都至关重要。希望这篇教程能帮你打下坚实基础！

—— 学习愉快，编程不止！ ——