计数质数

[YalongYan]

题目链接： 204. 计数质数

质数定义

质数是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数

正确代码

var countPrimes = function(n) {
    let arr = new Array(n).fill(1) // 默认都是1质数，0就不是质数
    let count = 0
    for(i = 2; i < n; i++) {
        if(arr[i]) {
            count++
            // for(j = 2 * i; j < n; j+=i) {  // 这个也是可以的
            for(j = i * i; j < n; j+=i) {
                arr[j] = 0
            }
        }
    } 
    return count
}

笨方法-会导致超时，不推荐

var countPrimes = function(n) {
    let isNum = (num) => {
        for (let i=2; i*i <= num; i++) {
            if (num % i === 0) {
                return false
            }
        }
        return true
    }
    let result = 0
    for(let i=2; i<n; i++) {
        if (isNum(i)) {
            result++
        }
    }
    return result
};