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

示例

示例 1：

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

输入：n = 0
输出：0
示例 3：

输入：n = 1
输出：0

题解

建立一个数组，长度为n，填充为1
[1,1,1,1,1,1,1,1,1,1]

从下标2开始遍历，将 2 的倍数下标都置为0
[1,1,1,1,0,1,0,1,0,1]

再遍历下标3，将 3 的倍数下标都置为0，遇到 0 直接跳过
[1,1,1,1,0,1,0,1,0,0]

直到遍历结束，筛选出数字仍然为 1 的个数，在排除掉 0 和 1 下标

  1. /**
  2.  * @param {number} n
  3.  * @return {number}
  4.  */
  5. var countPrimes = function(n) {
  6.     if (n === 0 || n === 1) {
  7.         return 0
  8.     }
  9.     const list = new Array(n).fill(1)
  11.     for (let i = 2; i < list.length; i++) {
  12.         if (list[i]) {
  13.             for (let j = 2 * i; j < n; j += i) {
  14.                 list[j] = 0
  15.             }
  16.         }
  17.     }
  19.     return list.filter(item => item > 0).length - 2
  20. };

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