计数质数
原创
题目
难度级别：简单
统计所有小于非负整数 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
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
