在Rust中实现编译期固定大小数组的埃拉托斯特尼筛法

要实现编译期确定大小的数组版本筛法，你需要利用Rust的const泛型特性——它允许将编译期常量作为函数的泛型参数，以此让数组大小在编译时确定。

正确实现示例 #

/// 获取小于等于 MAX 的所有素数，MAX 必须是编译期常量
fn eratosthenes_primes<const MAX: usize>() -> Vec<usize> {
    // 初始化数组：默认标记所有数为素数（true），0和1除外
    let mut is_prime = [true; MAX + 1];
    is_prime[0] = false;
    if MAX >= 1 {
        is_prime[1] = false;
    }

    // 埃拉托斯特尼筛法核心逻辑
    for i in 2..=((MAX as f64).sqrt() as usize) {
        if is_prime[i] {
            // 标记i的所有倍数为非素数
            for j in (i*i..=MAX).step_by(i) {
                is_prime[j] = false;
            }
        }
    }

    // 收集所有素数
    is_prime.iter()
        .enumerate()
        .filter(|(_, &prime)| prime)
        .map(|(num, _)| num)
        .collect()
}

fn main() {
    // 调用时指定编译期常量大小，比如筛选100以内的素数
    let primes = eratosthenes_primes::<100>();
    println!("100以内的素数：{:?}", primes);
}

关键说明 #

• 函数通过const MAX: usize定义泛型参数，确保MAX是编译期可知的常量，这样数组[true; MAX + 1]的大小能被编译器提前确定。
• 调用函数时必须显式指定MAX的值，或者使用已定义的编译期常量：

  const MAX_LIMIT: usize = 200;
  let primes = eratosthenes_primes::<MAX_LIMIT>();
  

• 注意栈空间限制：数组分配在栈上，如果MAX过大（比如超过数万）会导致栈溢出。这种场景建议改用Vec，但你的需求是硬编码且编译期确定的小范围场景，数组完全适用。

内容的提问来源于stack exchange，提问作者Pioneer_11