素数个数

题目¶

[204] 计数素数：统计所有小于非负整数 n 的质数的数量。

暴力法¶

/**
 * @param {number} n
 * @return {number}
 */
var countPrimes = function(n) {
  let count = 0;
  for(let i = 2; i < n; i++) {
    if (isPrime(i)) {
      count++;
    }
  }

  return count;
};

function isPrime(x) {
  for(let i = 2; i <= Math.sqrt(x); i++) {
    if (x % i === 0) {
      return false;
    }
  }

  return true;
}

埃式筛选法¶

var countPrimes = function(n) {
  let count = 0;
  const composite = Array(n).fill(false); // 记录合数

  for(let i = 2; i < n; i++) {
    if (composite[i]) {
      continue;
    }

    count++;
    for (let j = i; i * j < n; j++) {
      composite[i * j] = true; 
    }
  }

  return count;
};