204. Count Primes

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

思路：x是质数，那么大于x的x的倍数 2x，3x一定不是质数，假如 isPrime[x]表示数 x 是不是质数，从小到大遍历每个数，如果这个数为质数，将所有倍数标记为合数，在运行结束的时候可以知道质数的个数。为了减少重复的计数，可以从根号n 开始。

• 时间复杂度 ，空间复杂度O(n)
• Runtime: 275 ms, faster than 60.51%
• Memory Usage: 79 MB, less than 71.99%

/**
 * @param {number} n
 * @return {number}
 */
var countPrimes = function(n) {
  if (n <= 2) {
    return 0;
  }
  let isPrime = Array(n).fill(false);
  let boundary = Math.floor(Math.sqrt(n));
  for (let i = 2; i <= boundary; i++) {
    if (isPrime[i] === false) {
      for (let j = i * 2; j < n; j = j + i) {
        isPrime[j] = true;
      }
    }
  }
  
  let res = 0;
  for (let i = 2; i < n; i++) {
    if (isPrime[i] === false) {
      res++;
    }
  }
  return res;
};