算法自由之路

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, … 一定不是质数，因此我们可以从这里入手。