All files / leetCode 0204.ts

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
3x
2x
 
1x
1x
1x
 
 
1x
4x
4x
 
 
 
1x
 
 
export default function countPrimes(n: number): number {
  if (n <= 1)
    return 0
 
  const prime = Array.from<boolean>({ length: n }).fill(true)
  prime[0] = false
  prime[1] = false
 
  // 筛子法求质数
  for (let i = 0; i < Math.sqrt(n); i++) {
    if (prime[i]) {
      for (let j = i * i; j < n; j += i) prime[j] = false
    }
  }
 
  return prime.filter(Boolean).length
}