1. 首页
  2. IT资讯

【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
};

本文来自投稿,不代表程序员编程网立场,如若转载,请注明出处:http://www.cxybcw.com/199890.html

联系我们

13687733322

在线咨询:点击这里给我发消息

邮件:1877088071@qq.com

工作时间:周一至周五,9:30-18:30,节假日休息

QR code