Rust素数筛程序效率极低（--release模式下仍慢）求优化

一、性能慢的核心原因 #

1. Vec的remove操作效率极低：numbers.remove()是O(n)复杂度，每次移除元素都要移动后面所有元素，多次调用后总复杂度会变成O(n²)，数据量大时性能急剧下降。
2. 生成待移除数字的逻辑冗余：双层循环for i in 2..ceiling_root+1 + for j in i..user_input+1会生成大量重复值（比如6会被23和32各生成一次），虽然后面用dedup去重，但生成过程本身就浪费大量时间，且没有从i的平方开始遍历，做了很多无用计算。
3. 重复遍历检查：numbers.iter().any()和numbers.iter().position()都是全量遍历Vec，每次移除都要两次遍历，进一步加剧性能损耗。

二、优化方案（埃氏筛正确实现） #

埃氏筛的核心是用布尔数组标记非素数，而非反复修改Vec。以下是优化后的代码：

main.rs优化版 #

mod math;
mod user_input;

fn main() {
    let max = user_input::get_user_input("Enter a positive integer: ");
    if max < 2 {
        println!("Prime numbers up to {}: []", max);
        return;
    }

    // 初始化筛子：索引对应数字，值表示是否为素数，初始全设为true，0和1除外
    let mut sieve = vec![true; (max + 1) as usize];
    sieve[0] = false;
    sieve[1] = false;

    let ceiling_root = (max as f64).sqrt() as usize;
    for i in 2..=ceiling_root {
        if sieve[i] {
            // 从i*i开始标记i的倍数，步长i
            for j in (i*i..=max as usize).step_by(i) {
                sieve[j] = false;
            }
        }
    }

    // 收集所有标记为true的索引（即素数）
    let primes: Vec<i32> = sieve.iter()
        .enumerate()
        .filter(|(_, &is_prime)| is_prime)
        .map(|(num, _)| num as i32)
        .collect();

    println!("Prime numbers up to {}: {:?}", max, primes);
}

math.rs简化 #

原number_to_vector函数可以用迭代器直接简化，甚至在优化后的逻辑中可以完全移除该函数：

pub fn number_to_vector(number: i32) -> Vec<i32> {
    (1..=number).collect()
}

三、Rust实用编码规范与窍门 #

1. 省略不必要的return：Rust函数默认返回最后一行表达式，无需显式写return。例如get_user_input可简化为：

pub fn get_user_input(prompt: &str) -> i32 {
    println!("{}", prompt);
    let mut user_input = String::new();
    io::stdin().read_line(&mut user_input).expect("Failed to read line");
    user_input.trim().parse().expect("Please enter an integer!")
}

2. 处理边界情况：原代码未考虑输入小于2的场景，会引发潜在panic，优化后的代码加入了边界判断。
3. 优先使用迭代器：Rust迭代器经过性能优化，且代码更简洁。比如收集素数时用enumerate()+filter()+map()的链式调用。
4. 替换unwrap()的错误处理：生产环境尽量避免unwrap()，可用match或if let处理错误。例如get_user_input可返回Result类型：

pub fn get_user_input(prompt: &str) -> Result<i32, String> {
    println!("{}", prompt);
    let mut user_input = String::new();
    io::stdin().read_line(&mut user_input)
        .map_err(|e| format!("Failed to read line: {}", e))?;
    user_input.trim().parse()
        .map_err(|e| format!("Please enter an integer! Error: {}", e))
}

然后在main中处理结果：

fn main() {
    let max = match user_input::get_user_input("Enter a positive integer: ") {
        Ok(num) if num > 0 => num,
        Ok(_) => {
            println!("Please enter a positive integer greater than 0!");
            return;
        },
        Err(e) => {
            println!("{}", e);
            return;
        }
    };
    // 后续筛法代码...
}

5. 变量命名更直观：原代码中user_input作为数字变量名不够清晰，改为max或upper_limit更易懂。

四、性能差距说明 #

当输入10000时：

• 原代码生成的numbers_to_remove会产生大量重复值，排序和去重耗时久；每次移除元素都要移动Vec内的元素，累计数百万次操作；
• 优化后的布尔数组版本，标记非素数的时间复杂度为O(n log log n)，收集素数为O(n)，性能会随着输入增大呈指数级领先。

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