204.计数质数

链接：204.计数质数
难度：Medium
标签：数组、数学、枚举、数论
简介：统计所有小于非负整数 n 的质数的数量。

题解 1 - typescript

• 编辑时间：2020-12-03
• 执行用时：136ms
• 内存消耗：52.1MB
• 编程语言：typescript
• 解法介绍：埃氏筛。

function countPrimes(n: number): number {
  const isPrime = new Array(n).fill(1);
  let ans = 0;
  for (let i = 2; i < n; ++i) {
    if (isPrime[i]) {
      ans += 1;
      for (let j = i * i; j < n; j += i) {
        isPrime[j] = 0;
      }
    }
  }
  return ans;
}

题解 2 - typescript

• 编辑时间：2021-08-20
• 执行用时：256ms
• 内存消耗：109.5MB
• 编程语言：typescript
• 解法介绍：分别统计每个数的倍数快速标记。

function countPrimes(n: number): number {
  const arr: boolean[] = new Array(n).fill(true);
  arr[0] = arr[1] = false;
  for (let i = 2; i <= n - 1; i++) {
    if (arr[i]) for (let num = 2; num * i < n; num++) arr[num * i] = false;
  }
  return arr.filter(Boolean).length;
}