高效计算欧拉函数（Rust语言实现详解）

什么是欧拉函数？

欧拉函数通常记作 φ(n)。例如：

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

欧拉函数的数学性质

欧拉函数具有以下重要性质，这些性质是高效实现的基础：

1. 如果 p 是质数，则 φ(p) = p - 1。
2. 如果 p 是质数且 k ≥ 1，则 φ(pᵏ) = pᵏ - pᵏ⁻¹。
3. 如果 m 和 n 互质，则 φ(mn) = φ(m) × φ(n)（积性函数）。

Rust 实现欧拉函数

我们将提供两种实现方式：一种是简单直观的暴力法（适合理解），另一种是基于质因数分解的高效算法（适合实际应用）。

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

遍历 1 到 n 的所有数字，检查是否与 n 互质（即最大公约数为 1）。

fn gcd(a: u64, b: u64) -> u64 {    if b == 0 {        a    } else {        gcd(b, a % b)    }}fn euler_phi_brute(n: u64) -> u64 {    if n == 0 { return 0; }    let mut count = 0;    for i in 1..=n {        if gcd(n, i) == 1 {            count += 1;        }    }    count}

这个方法的时间复杂度是 O(n log n)，对于大数来说效率较低，但逻辑清晰，非常适合学习 Rust欧拉函数 的基本概念。

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

利用欧拉函数的公式：若 n = p₁ᵏ¹ × p₂ᵏ² × … × pₘᵏᵐ，则

φ(n) = n × (1 - 1/p₁) × (1 - 1/p₂) × … × (1 - 1/pₘ)

fn euler_phi(n: u64) -> u64 {    if n == 0 { return 0; }    let mut result = n;    let mut temp = n;    let mut p = 2;    while p * p <= temp {        if temp % p == 0 {            while temp % p == 0 {                temp /= p;            }            result -= result / p;        }        p += 1;    }    if temp > 1 {        result -= result / temp;    }    result}

这个算法的时间复杂度为 O(√n)，远优于暴力法。它是 Rust数论算法 中的经典实现，也是实际项目中推荐使用的方式。

完整测试示例

下面是一个完整的 Rust 程序，包含测试用例：

fn main() {    let test_cases = [1, 6, 9, 10, 12, 17];    for &n in &test_cases {        println!("φ({}) = {}", n, euler_phi(n));    }}// 此处插入上面定义的 euler_phi 函数

运行结果应为：

φ(1) = 1φ(6) = 2φ(9) = 6φ(10) = 4φ(12) = 4φ(17) = 16

为什么选择 Rust 实现欧拉函数？

Rust 以其内存安全、零成本抽象和高性能著称，非常适合实现数学算法。通过学习 欧拉函数实现，你不仅能掌握数论知识，还能熟悉 Rust 的所有权、模式匹配和函数式编程特性。

结语

本文详细讲解了如何在 Rust 中实现欧拉函数，从基础概念到高效算法，适合编程新手和有一定经验的开发者。希望这篇 Rust编程教程 能帮助你更好地理解数论与系统编程的结合。动手试试吧！

掌握核心算法，开启高效编程之旅！