204. 计数质数.md

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

示例:

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

思路：

• 如果使用暴力解，时间复杂度为O(n2)，不可取
• 使用埃拉托斯特尼筛法，遍历一遍，把质数倍数剔除

solution:

1. 第一版

/**
 * @param {number} n
 * @return {number}
 */
var countPrimes = function(n) {
    const isPrim = Array.from({ length: n }, () => true)
    for(let i = 2; i < n; i++) {
        if (isPrim[i]) {
            for (let j = i * 2; j < n; j += i) {
                isPrim[j] = false
            }
        }
    }
    let count = 0
    for (let i = 2; i < n; i++) {
        isPrim[i] && (count++)
    }
    return count
};

• 有个疑问，同样的代码，使用Array.from生成待遍历数组，会慢很多，而用ES2017的Uint8Array生成无符号整数数组，会快很多

2. 第二版

/**
 * @param {number} n
 * @return {number}
 */
var countPrimes = function(n) {
    const isPrim = new Uint8Array(n)
    let count = 0
    for (let i = 2; i < n; i++) {
        if (!isPrim[i]) {
            count++
            for (let j = i * 2; j < n; j += i) {
                isPrim[j] = 1
            }
        }
    }
    return count
};