avatar

【LeetCode 204】计算质数

LeetCode 204 计算质数

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

示例:

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

思路:

引入一个算法,叫 厄拉多塞素数筛选法

23d348bef930ca4bb73f749500f664ccffc5e41467aac0ba9787025392ca207b-1

代码

Javascript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
var countPrimes = function(n) {
if (n < 2)
return 0;
//给所有的数值默认位false
let arr = new Array(n + 1);
let primeCount = 0;
for(let i = 2;i < n;i++){
//如果不是质数
if(!arr[i]){
primeCount++;
}
//循环排除所有i的倍数
//从i * 2开始,来排除
for (let j = i * 2;j < n;j = j + i){
arr[j] = true;
}
}
return primeCount;
};
文章作者: Lovely Ruby
文章链接: https://wangzhongqing.xyz/p/65040.html
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Ruby の いえ
打赏
  • 微信
    微信
  • 支付寶
    支付寶

评论