204.计数质数.md

204.计数质数

/*
 * @lc app=leetcode.cn id=204 lang=typescript
 *
 * [204] 计数质数
 */

// @lc code=start
function countPrimes(n: number): number {}
// @lc code=end

解法 1: 埃氏筛

• https://leetcode-cn.com/problems/count-primes/solution/ji-shu-zhi-shu-by-leetcode-solution/

function countPrimes(n: number): number {
  if (n <= 2) return 0

  let prime = new Array(n).fill(1)
  let res = 0
  for (let i = 2; i < n; i++) {
    if (!prime[i]) continue
    res++
    for (let j = i * i; j < n; j += i) {
      prime[j] = 0
    }
  }

  return res
}

解法 2: 线性筛

function countPrimes(n: number): number {
  if (n <= 2) return 0

  const primes = new Set<number>()
  const isPrime = new Array(n).fill(1)
  for (let i = 2; i < n; i++) {
    if (isPrime[i]) primes.add(i)
    for (const prime of primes) {
      if (i * prime >= n) break
      isPrime[i * prime] = 0
      if (!(i % prime)) break
    }
  }

  return primes.size
}

Case

test.each([
  { input: { n: 10 }, output: 4 },
  { input: { n: 0 }, output: 0 },
  { input: { n: 1 }, output: 0 },
  { input: { n: 2 }, output: 0 },
  { input: { n: 3 }, output: 1 },
  { input: { n: 20 }, output: 8 },
])('input: n = $input.n', ({ input: { n }, output }) => {
  expect(countPrimes(n)).toBe(output)
})