【一天一大 lee】计数质数 (难度:简单) - Day20201203

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

输入：n = 0
输出：0

输入：n = 1
输出：0

/**
 * @param {number} n
 * @return {number}
 */
var countPrimes = function(n) {
    if (n < 2) return 0
    let _result = 0
    for (let i = 2; i < n; ++i) {
        _result += isPrime(i)
    }
    // 判断是否是质数
    function isPrime(num) {
        let index = 2,
            max = Math.sqrt(num)
        while (index <= max) {
            if (num % index == 0) return false
            index++
        }
        return true
    }
    return _result
}

var countPrimes = function(n) {
    if (n < 2) return 0
    let isPrime = Array(n).fill(true),
        _result = 0
    for (let i = 2; i < n; ++i) {
        if (isPrime[i]) {
            _result += 1
            let index = i * i
            while (index < n) {
                isPrime[index] = false
                index += i
            }
        }
    }
    return _result
}