rust - 为什么我的素数筛法包括数字 49？

Question

我没能在我的筛选实现中找到错误。我的测试显示以下错误。

// Expected 
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
// Mine
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 49]

有人可以指出我做错了什么吗？我意识到这与最终条件有关，但我一直无法弄清楚

/// Find all prime numbers less than `n`.
/// For example, `sieve(7)` should return `[2, 3, 5]`
pub fn sieve(n: u32) -> Vec<u32> {
    // Check assert and then populate vector
    assert!(n > 1, "Error n is less than 1");
    let mut is_prime: Vec<bool> = vec![true; (n-1) as usize];
    let sqrt: u32 = (n as f32).sqrt() as u32 + 1;
    for i in 2..sqrt {
        if is_prime[i as usize] == true {
            let mut k = i * i;
            loop {
                if k > n {
                    break;
                }
                is_prime[(k-2) as usize] = false;
                k += i;
                println!("i:{} k:{}", i, n);
            }
        }
    }
    let mut primes: Vec<u32> = Vec::new();
    for i in 0..is_prime.len() {
        if is_prime[i] == true {
            primes.push((i+2) as u32);
        }
    }
    println!("SQ{}", sqrt);
    println!("Vec {:?}", primes);
    primes
}

( Github )

另外，这是一个相对较快的实现还是我犯了一个大错误(除了打印，那些是为了调试)？

Answer 1

似乎您忽略值 0 和 1 的“聪明”技巧适得其反，并且您没有始终如一地上下移动偏移量。像这样的东西似乎给出了正确的输出:

fn sieve(n: u32) -> Vec<u32> {
    let mut is_prime = vec![true; (n-2) as usize];
    let sqrt = (n as f32).sqrt() as u32 + 1;
    for i in 2..sqrt {
        if is_prime[(i-2) as usize] {
            let mut k = i*i;
            loop {
                if k >= n {
                    break;
                }
                is_prime[(k-2) as usize] = false;
                k += i;
                println!("i:{} k:{}", i, n);
            }
        }
    }
    let mut primes = Vec::new();
    for i in 0..is_prime.len() {
        if is_prime[i] {
            primes.push((i+2) as u32);
        }
    }
    println!("SQ{}", sqrt);
    println!("Vec {:?}", primes);
    primes
}

fn main() {
    let a = sieve(50);
    assert_eq!(a, [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]);
}