筛法求素数

204. 计数质数

问题

统计所有小于非负整数 n 的质数的数量。

当我们判断一个数是否为素数时，通常我们需要循环判断该数除了1和它自己外没有其它的因子。判断一个数n需要循环次。对于该题而言，当n比较大时，也就当我们需要频繁判断一个数是否为素数时，这样的效率就不太高了，在leetcode上会超时。解决方法是我们可以先求出一定范围内的所有素数，然后直接判断一个数是否为素数，用空间换时间。这种方法叫做“埃拉托色尼筛法”。

我们用一个大小为 n + 1 的数组 primes 来保存素数表，primes[i] = true 表示 i 为素数。
具体做法是 primes 初始为 true，然后依次将下标 2 的倍数的置为 false，然后是3的倍数，5 的倍数，下一个素数的倍数 ……。最后留下的为true的都是素数。

代码

pub fn primes(n: i32) -> Vec<bool> {
    let mut primes = vec![true; n];
    primes[0] = false;
    primes[1] = false;
    for i in 2..n{
        // 因为[2,i-1] * i 已经被置为false了, 但i * i > n，所已比i大的数的倍数中比n小的都已经处理过了
        if i*i > n {
            break;
        }
        if primes[i] {
            // 这里j也从i*i开始就行，j每次递增i，即i的倍数
            for j in (i*i..=n).step_by(i){
                primes[j] = false;
            }
        }
    }
    primes
}