204. 计数质数

发表于 分类于 阅读次数：

统计所有小于非负整数 n 的质数的数量。

示例 1：

1
2
3
输入：n = 10
输出：4
解释：小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。

示例 2：

1
2
输入：n = 0
输出：0

示例 3:

1
2
输入：n = 1
输出：0

枚举

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * @param {number} n
 * @return {number}
 */
var countPrimes = function (n) {
  let ans = 0;
  for (let i = 2; i < n; i++) {
    ans += isPrime(i);
  }
  return ans;
};

var isPrime = function (x) {
  for (let i = 2; i * i <= x; i++) {
    if (x % i === 0) {
      return false;
    }
  }
  return true;
};