204. 计数质数

• 题号：204
• 来源：LeetCode
• 难度：中等
• 标签：数学 数组
• 语言：TypeScript
• 解法：1 个
• 作者：lmliheng
• 最近更新：2026-09-27

TypeScript · O(n*log(log n)) 时间 · O(n) 空间 · 更新于 2026-09-27

埃氏筛，从 i*i 起标记合数

/**
 * @difficulty medium
 * @tags 数学,数组
 * @time O(n*log(log n))
 * @space O(n)
 * @note 埃氏筛，从 i*i 起标记合数
 * @204. 计数质数
 */
function countPrimes(n: number): number {
    if (n <= 2) return 0
    let isPrime = new Array(n).fill(true)
    isPrime[0] = false
    isPrime[1] = false
    for (let i = 2; i * i < n; i++) {
        if (isPrime[i]) {
            for (let j = i * i; j < n; j += i) {
                isPrime[j] = false
            }
        }
    }
    let count = 0
    for (let i = 2; i < n; i++) {
        if (isPrime[i]) count++
    }
    return count
}

源码：ts/leetcode/204. 计数质数.ts

---

在 GitHub 上查看题目所在目录：lmliheng/algorithm