美文网首页
计数质数

计数质数

作者: 422ccfa02512 | 来源:发表于2020-12-06 23:21 被阅读0次

    题目

    难度级别:简单

    统计所有小于非负整数 n 的质数的数量。

    示例 1:

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

    示例 2:

    输入:n = 0
    输出:0

    示例 3:

    输入:n = 1
    输出:0

    提示:

    0 <= n <= 5 * 106

    解题思路

    埃氏筛

    若一个数为质数,则它的n倍就一定是一个合数。初始化数组isPrimes,数量为n,每一项赋值为1。遍历数组isPrimes,当它为1时说明是一个质数,之后求出它的n倍,并赋值0。

    const countPrimes = function(n) {
        const isPrimes = new Array(n).fill(1)
        let count = 0
    
        for(let i = 2; i < isPrimes.length; i++) {
            if (isPrimes[i]) {
                count++
                for(let j = i * i; j < n; j = j + i) {
                    isPrimes[j] = 0
                }
            }
        }
    
        return count
    };
    

    线性筛

    与埃氏筛的基础上在创建质数primes数组,当在isPrimes里遇到值为1的质数时,将其添加至primes数组。同时遍历primes数组,因为primes内是质数,所以乘上任何数都是合数。当遇到 isPrimes的第i项 % primes[j]的值为0时,后面的数之前的数已经计算过,跳出循环。

    const countPrimes = function(n) {
        const isPrimes = new Array(n).fill(1)
        const primes = []
        
        for(let i = 2; i < isPrimes.length; i++) {
            if (isPrimes[i]) primes.push(i)
            
            for(let j = 0; j < primes.length && i * primes[j] < n; j++) {
                isPrimes[i * primes[j]] = 0
                if (i % primes[j] === 0) break
            }
        }
    
        return primes.length
    };
    

    题目来源:力扣(LeetCode)
    链接:https://leetcode-cn.com/problems/count-primes

    相关文章

      网友评论

          本文标题:计数质数

          本文链接:https://www.haomeiwen.com/subject/sogawktx.html