共计 508 个字符,预计需要花费 2 分钟才能阅读完成。
统计所有小于非负整数 n 的质数的数量。
示例:
输出: 10
输入: 4
解释: 小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7。
js 暴力解法:
/**
* @param {number} n
* @return {number}
*/
var countPrimes = function(n) {
var count = 0;
function isPrime(num){for(var i=2;i<=Math.sqrt(num);i++){if(num%i===0) return false
}
return true
}
for(var j=2;j<n;j++){if(isPrime(j)){count++}
}
return count
};
js 埃拉托斯特尼筛法
/**
* @param {number} n
* @return {number}
*/
var countPrimes = function(n) {
var count = 0;
var times = Array(n).fill(0);
for(var i =2;i<times.length;i++){if(!times[i-1]){
count++;
for(var j=i*i;j<=n;j+=i){times[j-1]=true
}
}
}
return count
};
正文完