探索素数的奥秘（Rust语言中的高效素数判定算法详解）

什么是素数？

素数是像 2、3、5、7、11、13……这样的数字。注意：1 不是素数，因为它只有一个正因数；2 是唯一的偶素数。

方法一：暴力法（最直观但效率低）

最简单的思路是从 2 到 n-1 遍历所有数字，看是否能整除 n。如果都不能整除，那么 n 就是素数。

// 暴力法判断素数fn is_prime_brute(n: u64) -> bool {    if n <= 1 {        return false;    }    if n == 2 {        return true;    }    for i in 2..n {        if n % i == 0 {            return false;        }    }    true}

这个方法对小数字有效，但当 n 很大时（比如百万级别），速度会非常慢。时间复杂度为 O(n)，效率低下。

方法二：优化到平方根（推荐入门使用）

一个关键数学性质：如果 n 有因数，那么至少有一个因数 ≤ √n。因此我们只需检查到 √n 即可。

use std::f64;fn is_prime_sqrt(n: u64) -> bool {    if n <= 1 {        return false;    }    if n == 2 {        return true;    }    if n % 2 == 0 {        return false; // 排除所有偶数    }    let limit = (n as f64).sqrt() as u64 + 1;    for i in (3..=limit).step_by(2) { // 只检查奇数        if n % i == 0 {            return false;        }    }    true}

这个版本跳过了所有偶数（除了2），并将循环上限设为 √n，大大提升了效率。时间复杂度降为 O(√n)。这是Rust初学者指南中最实用的方法之一。

方法三：埃拉托斯特尼筛法（批量生成素数）

如果你需要找出某个范围内的所有素数（比如1到100万），使用素数算法中的经典——埃拉托斯特尼筛法（Sieve of Eratosthenes）会更高效。

fn sieve_of_eratosthenes(limit: usize) -> Vec {    let mut is_prime = vec![true; limit + 1];    is_prime[0] = false;    if limit >= 1 {        is_prime[1] = false;    }    for i in 2..=((limit as f64).sqrt() as usize) {        if is_prime[i] {            let mut j = i * i;            while j <= limit {                is_prime[j] = false;                j += i;            }        }    }    is_prime}// 使用示例：找出100以内的所有素数fn main() {    let primes = sieve_of_eratosthenes(100);    for (num, &prime) in primes.iter().enumerate() {        if prime {            println!("{} 是素数", num);        }    }}

筛法适合批量处理，时间复杂度约为 O(n log log n)，非常适合需要频繁查询素数的场景。

性能对比与选择建议

• 单个大数判断：使用“优化到平方根”方法（方法二）。
• 批量生成小范围素数：使用埃拉托斯特尼筛法（方法三）。
• 超大数（如密码学用途）：需使用米勒-拉宾等概率算法（超出本文范围）。

总结

通过本文，你已经掌握了在Rust素数判定中的三种核心方法。无论你是刚接触Rust编程教程的新手，还是想优化已有代码的开发者，这些技巧都能帮助你写出更高效的程序。记住：理解算法背后的数学原理，比死记代码更重要！

动手试试吧！修改上面的代码，测试不同数字，观察运行时间。编程的乐趣就在于实践！