掌握Rust中的最大公约数算法（从零开始学习GCD实现与欧几里得算法）

什么是最大公约数？

最大公约数是指两个或多个整数共有约数中最大的一个。例如，12和18的公约数有1、2、3、6，其中最大的是6，因此gcd(12, 18) = 6。

欧几里得算法原理

欧几里得算法（又称辗转相除法）是计算GCD最高效的方法之一。其核心思想基于以下定理：

gcd(a, b) = gcd(b, a mod b)，当 b ≠ 0；若 b = 0，则 gcd(a, 0) = a。

这个过程不断重复，直到余数为0，此时的非零数就是最大公约数。

Rust中实现GCD算法

下面我们用Rust语言来实现这个算法。Rust是一门内存安全、高性能的系统编程语言，非常适合学习算法。

方法一：递归实现

fn gcd_recursive(a: u32, b: u32) -> u32 {    if b == 0 {        a    } else {        gcd_recursive(b, a % b)    }}fn main() {    let x = 48;    let y = 18;    println!("gcd({}, {}) = {}", x, y, gcd_recursive(x, y));}

这段代码使用了递归方式。当 b 为0时，直接返回 a；否则继续调用自身，参数变为 (b, a % b)。

方法二：迭代实现（更高效，避免栈溢出）

fn gcd_iterative(mut a: u32, mut b: u32) -> u32 {    while b != 0 {        let temp = b;        b = a % b;        a = temp;    }    a}fn main() {    let x = 48;    let y = 18;    println!("gcd({}, {}) = {}", x, y, gcd_iterative(x, y));}

迭代版本使用 while 循环，不断更新 a 和 b 的值，直到 b 变为0。这种方式不会因为递归深度过大而导致栈溢出，更适合处理大数。

使用Rust标准库

其实，Rust标准库已经为我们提供了GCD函数！从Rust 1.60开始，u32、u64 等整数类型内置了 .gcd() 方法：

fn main() {    let x = 48u32;    let y = 18u32;    println!("gcd({}, {}) = {}", x, y, x.gcd(y));}

不过，作为学习者，亲手实现一遍算法能帮助你更深入理解编程新手学Rust的过程和底层逻辑。

小结

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

• 最大公约数的定义
• 欧几里得算法的核心思想
• 如何在Rust中用递归和迭代两种方式实现Rust GCD实现
• 如何使用Rust标准库简化开发

无论你是为了面试准备，还是为了夯实算法基础，掌握Rust最大公约数算法都是一个很好的起点。继续练习，尝试用不同数据类型（如 i32、u64）扩展你的函数吧！

关键词回顾：Rust最大公约数算法、Rust GCD实现、欧几里得算法Rust、编程新手学Rust