题目

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

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

思路一

我们这里先假设从1到n，全是质数，然后我们再依次相乘，把约数排除出去就可以了，我们这里先判断一下当前n形参是否小于或者等于2，如果是则直接返回0，接下来我们使用new Array方法创建一个长度为形参n的空数组，使用fill方法使其默认值全为1，如果我们不这样进行默认值，后来我们通过索引获取的时候，会常建新值，比较消耗性能，所以我们这里就一次性把数组建好，然后我们在声明一个num变量，他的值是n-2，然后我们进行循环，循环的停止条件为i * i < n，这是因为两个数的相乘的到 n，这两个数必然是一个数大于或者等于n，一个数小于或者等于n，或者两个数都等于n，在循环中我们设定调出条件，如果tempArr[i]和0相等，那么则说明 i 是约数，说明 i 是两个比它小的数的乘积，那么所有能被 i 整除的数们，必然也能被那两个数整除，我们这里直接跳过当前循环即可，然后再声明一个j变量，当前的j变量的值是i，然后再声明一个循环，第二个循环使用的是j变量，因为如果当前的i变量是10，那么说明当前两个数的乘积的式子，所有比10小的数都已经计算过了，那么我们就直接从当前i变量开始即可，我们第二个循环如果当前乘积结果大于n的j变量，那么我们则不需要在往下计算了，然后再让num变量进行自减1，最后我们将num变量返回出去即可

var countPrimes = function(n) {
  if (n <= 2) return 0
  let tempArr = new Array(n).fill(1)
  let num = n - 2
  for (let i = 2; i * i < n; i++) {
    if (tempArr[i] === 0) continue
    let j = i
    for (; j * i < n; j++) {
      let thsNum = i * j
      if (!tempArr[thsNum]) continue
      tempArr[thsNum] = 0
      num--
    }
  }
  return num
}