204.计数质数-easy-欧拉筛

统计所有小于非负整数 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

思路：
首先预处理出5 10内的素数（用欧拉筛出质数即可），然后二分查找答案，因为leetcode类似于调用函数的形式进行测试，所以在全局变量中预处理的答案，可以供下一次调用直接使用。
复杂度分析：
时间复杂度 首次执行时：O(π(5 10) + 5 10+ log**π(N)),随后的调用：O(logπ(N)**) 其中 π(X) 为「质数计数函数」，表示不超过 X 的质数个数。N是输入。「欧拉筛法」的时间复杂度为 O(N)；如果遍历下面保存是否为素数的数组notPrime,来统计素数个数，时间复杂度应为**O(2n)，常数大一点，二分查找素数数组只需O(logπ(N)**）的时间复杂度。
优化前：

优化后：
空间复杂度 O(N + π(N)) 需要π(N)空间保存素数数组，O(N）空间记录每个数是否为素数。

/**
 * @param {number} n
 * @return {number}
 */
const max = 5*1e6;
const notPrimse = new Int32Array(max + 5);
const prime = [];
let count = 0;
for(let i = 2 ; i <= max; i++) {
  if (!notPrimse[i]) {
    prime.push(i);
    count++;
  }
    for(let j = 0,k; j < count && (k = prime[j] * i) <= max; j++) {
        notPrimse[k] = 1;
        if(i % prime[j] === 0) {
          break;
        }
    }
}
var countPrimes = function(n) {
  let l = 0, r = count;
  while(l <= r) {
    const mid = (l + r) >> 1;
    if(prime[mid] > n) {
      r = mid - 1;
    } else if(prime[mid] === n){
      l = mid;
      break;
    } else {
      l = mid + 1;
    }
  }
  return l;
};