【leetcode】204. 计数质数 暴力 & 埃拉托斯特尼法

统计所有小于非负整数 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

};

以上是 【leetcode】204. 计数质数 暴力 &amp; 埃拉托斯特尼法 的全部内容, 来源链接: www.h5w3.com/37729.html

回到顶部