204. 计数质数
题目：
统计所有小于非负整数 n 的质数的数量。
解答：
-
方法一：暴力遍历 - 超时
时间复杂度：O(n*sqrt(n))，空间复杂度：O(1)
var countPrimes = function (n) {
let times = 0;
if (n < 2) {
return 0
}
let isZhi = (x) => {
// 2 为质数
if (x === 2) {
return true;
}
// 遍历的最大值 为根号x，算是小小的优化
for (let i = 2; i <= Math.sqrt(x); i++) {
if (x % i === 0) {
return false;
}
}
return true
}
for (let i = 2; i < n; i++) {
if (isZhi(i)) {
times += 1;
}
}
return times
};
- 方法二：埃氏筛
时间复杂度：O(nlogn)，空间复杂度：O(n)[需要 O(n)的空间记录每个数是否为质数]
-
主要逻辑：
从小到大遍历每个数，如果是质数 -> 将该质数的所有倍数都标记为 合数（除了该质数本身）
-
优化点：
从质数的 2倍 开始标记是冗余的，应该从 x·x 开始标记，因为 2x、3x…在之前肯定被标记过了
let countPrimes = (n) => {
if (n < 2) {
return 0
}
let isPrime = new Array(n).fill(1); // 默认所有数为质数
let res = 0; // 质数数量
for(let i = 2; i < n; i++) {
// 如果当前数为质数
if(isPrime[i]) {
res += 1;
// i * i - 很精髓，因为 i 的那些小于 i 的倍数，如 2i、3i 一定已经被标记过了
// j += i - 标记小于 n 的，当前质数的所有质数为合数
for(let j = i * i; j < n; j += i) {
isPrime[j] = 0;
}
}
}
return res
}