# 原题

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

示例:

输入: 10
输出: 4
解释: 小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。

# 解 :

var countPrimes = function (n) {
    if (n < 3) return 0 //1、2 不为质数
    //新生成数组,如 n=3 ,生成 [1,2,3]
    let result = [...new Array(n).keys()]
    //排除 1、2
    result[0] = result[1] = null
    //厄拉多塞解法,筛选质数
    for (let i = 2; i < n; i++) {
        if (result[i]) {
            for (let j = 2; i * j <= n; j++) {
                result[j * i] = null
            }
        }
    }
    //筛选出 不为null的数,即筛选出质数
    result = result.filter(item => {
        return item != null
    })
    return result.length
};

厄拉多塞解法 : 详情 (opens new window)

Last Updated: 4/3/2020, 6:21:54 PM