埃拉托斯特尼筛法

埃拉托斯特尼筛法(sieve of Eratoshenes)，简称埃氏筛，也称素数筛。这是一种简单且历史悠久的筛法，用来寻找一定范围内所有的质数。

原理：从2开始，将每个质数的各个倍数都标记为合数。一个质数的各个倍数，是一个差为此质数本身的等差数列。

提示

埃氏筛与试除法的区别在于，埃氏筛是以质数来测试每个待测数是否能被整除。

算式

给出要筛数值的范围n，找出平方根n以内的质数。

• 先用2去筛，即把2留下，把2的倍数剔除掉；
• 再用下一个质数，也就是3筛，把3留下，把3的倍数剔除掉；
• 接下去用下一个质数5筛，把5留下，把5的倍数剔除掉；
• 不断重复下去......

效果图

代码实现

/**
 * @param {number} n
 * @return {number}
 */

const countPrimes = function(n) {
    // 默认全部数为质数
    const arr = Array(n).fill(true);
    let count = 0;

    // 优化算法，最小因子为2，最大因子平方不会超过数
    for(let i = 2; i * i < n; i++) {
        // 如果数字为质数
        if(arr[i]) {
            // 将其倍数都标记为合数
            // 等差数列：j += i
            for(let j = i * i; j < n; j += i) {
                arr[j] = false;
            }
        }
    }

    for(let i = n; i >= 2; i--) {
        if(arr[i]) {
            count += 1;
        }
    }

    return count;
};