204.计数质数

计数质数

给定整数 n，返回所有小于非负整数 n 的质数的数量。

解析

埃拉托斯特尼筛法。

var countPrimes = function (n) {
  const isPrime = new Array(n).fill(true);
  let count = 0;
  for (let i = 2; i < n; i++) {
    if (isPrime[i]) {
      count++;
      for (let j = i * i; j < n; j += i) isPrime[j] = false;
    }
  }
  return count;
};