最小公倍数轻松学（Rust语言实现详解）

什么是“最小公倍数”？

两个或多个整数的最小公倍数是指能够被这些整数整除的最小正整数。例如：

• 4 和 6 的公倍数有：12、24、36……
• 其中最小的是 12，所以 LCM(4, 6) = 12

最小公倍数与最大公约数的关系

在计算 LCM 时，我们通常会借助最大公约数（GCD）。它们之间有一个重要的数学公式：

这意味着，只要我们能求出两个数的最大公约数，就能快速算出它们的最小公倍数。

用 Rust 实现最大公约数（GCD）

Rust 标准库其实已经提供了 gcd 方法（在较新版本中），但我们先手动实现一个，以便理解原理。这里使用经典的欧几里得算法：

fn gcd(mut a: u64, mut b: u64) -> u64 {    while b != 0 {        let temp = b;        b = a % b;        a = temp;    }    a}

这段代码通过不断取余操作，直到其中一个数变为 0，此时另一个数就是最大公约数。

用 Rust 实现最小公倍数（LCM）

有了 GCD 函数，我们就可以轻松写出 LCM 函数了。注意要处理乘法可能溢出的问题，但在学习阶段我们先假设输入不会导致溢出：

fn lcm(a: u64, b: u64) -> u64 {    if a == 0 || b == 0 {        return 0; // 0 和任何数的 LCM 是 0    }    a / gcd(a, b) * b // 先除后乘，避免溢出}

注意：我们写成 a / gcd(a, b) * b 而不是 a * b / gcd(a, b)，是为了减少中间结果溢出的风险。

完整示例程序

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

fn gcd(mut a: u64, mut b: u64) -> u64 {    while b != 0 {        let temp = b;        b = a % b;        a = temp;    }    a}fn lcm(a: u64, b: u64) -> u64 {    if a == 0 || b == 0 {        return 0;    }    a / gcd(a, b) * b}fn main() {    println!("LCM of 4 and 6 is: {}", lcm(4, 6));   // 输出 12    println!("LCM of 15 and 20 is: {}", lcm(15, 20)); // 输出 60    println!("LCM of 7 and 5 is: {}", lcm(7, 5));     // 输出 35}

使用 Rust 标准库（推荐方式）

从 Rust 1.60 开始，标准库在 num_integer crate 中提供了 lcm 和 gcd 方法。你也可以直接使用：

首先，在 Cargo.toml 中添加依赖：

[dependencies]num-integer = "0.1"

然后在代码中使用：

use num_integer::Integer;fn main() {    println!("LCM: {}", 4.lcm(&6)); // 输出 12}

总结

通过本文，你已经学会了如何在 Rust 中实现最小公倍数算法。这不仅帮助你掌握了一个重要的数学工具，也加深了对 Rust 语言基本语法和逻辑结构的理解。无论是面试题、算法竞赛，还是日常开发，Rust 算法教程中的这个知识点都非常实用。

记住，LCM 计算的核心在于理解它与 GCD 的关系，而 Rust 的简洁语法让实现变得清晰高效。希望这篇编程入门指南对你有所帮助！

关键词：Rust 最小公倍数, Rust 算法教程, LCM 计算, 编程入门