统计n以内素数的个数

素数是除1和其本身以外再无其它因子的数，0，1除外

一、素数的判定

function isPrime(x: number): boolean {
  // 判断 2 ~ sqrt(x) 内是否存在x的因子
  for (let i = 2; i * i <= x; ++i) {
    if (x % i === 0) return false;
  }
  return true;
}

二、统计n以内素数的个数

function stat(n: number): number {
  let count = 0;
  const map = {};
  for (let i = 2; i < n; ++i) {
    if (!map[i]) {
      if (isPrime(i)) count++;
      // 以下代码的功能是将能够预先知道是合数的数做个标记
      let k = i; // 从i开始计算，因为之前的 i * 1, i * 2, ..., i * (i - 1)已被标记
      while (i * k < n) {
        map[i * k] = true;
        k++;
      }
    }
  }
  return count;
}