204. 计数质数
统计所有小于非负整数 n
的质数的数量。
示例 1:
输入:n = 10
输出:4
解释:小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。
示例 2:
输入:n = 0
输出:0
示例 3:
输入:n = 1
输出:0
提示:
0 <= n <= 5 * 106
解法
一开始我写出这种解法。很显然。在 n 较大的时候就超时了
/**
* @param {number} n
* @return {number}
*/
var countPrimes = function (n) {
if (n === 0 || n === 1 || n === 2) {
return 0;
}
let index = 0;
function primeComputed(a) {
let data = true;
for (let i = 2; i < a; i++) {
if (a % i === 0) {
data = false;
}
}
return data;
}
for (let i = 2; i < n; i++) {
const isPrime = primeComputed(i);
isPrime ? index++ : "";
}
return index;
};
评论区的高级解法
var countPrimes = function (n) {
// 1 表示是质数, 0 表示是合数
const isPrime = new Array(n).fill(1);
let ans = 0;
for (let i = 2; i < n; ++i) {
if (isPrime[i]) {
ans += 1;
// 从 i^2 开始, 每次加 i
// 减少对 i 合数的标记次数
for (let j = i * i; j < n; j += i) {
isPrime[j] = 0;
}
}
}
return ans;
};
埃氏筛:该算法由希腊数学家厄拉多塞(EratosthenesEratosthenes)提出,称为厄拉多塞筛法,简称埃氏筛。
如果 x 是质数,那么大于 x 的 x 的倍数 2x,3x, … 一定不是质数,因此我们可以从这里入手。