题目
难度级别:简单
统计所有小于非负整数 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
网友评论