204. 计数质数

[buuing]

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

示例 1：

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

示例 2：

输入：n = 0
输出：0

示例 3：

输入：n = 1
输出：0

提示：

• 0 <= n <= 5 * 106

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/count-primes
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

---

• 暴力解题 (超时)

const countPrimes = n => {
  let nums = []
  for (let i = 2; i < n; i++) {
    let flag = true
    for (let num of nums) {
      let res = i / num
      if (res === ~~res) {
        flag = false
        break
      }
    }
    if (flag) nums.push(i)
  }
  return nums.length
}

• 哈希表

const countPrimes = n => {
  let arr = [], count = 0
  for (let i = 2; i < n; i++) {
    if (!arr[i]) {
      for (let j = i * i; j < n; j += i) {
        arr[j] = true
      }
      count++
    }
  }
  return count
}