0204. 计数质数【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 埃氏筛

1. 📝 题目描述

• leetcode

给定整数 n，返回 所有小于非负整数 n 的质数的数量。

---

示例 1：

输入：n = 10
输出：4
解释：小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7。

示例 2：

输入：n = 0
输出：0

示例 3：

输入：n = 1
输出：0

---

提示：

• 0 <= n <= 5 * 10^6

2. 🎯 s.1 - 埃氏筛

c

int countPrimes(int n) {
    if (n < 2) return 0;
    bool* isPrime = (bool*)malloc(sizeof(bool) * n);
    memset(isPrime, true, n);
    isPrime[0] = isPrime[1] = false;
    for (int i = 2; (long long)i * i < n; i++) {
        if (isPrime[i]) {
            for (int j = i * i; j < n; j += i) {
                isPrime[j] = false;
            }
        }
    }
    int count = 0;
    for (int i = 0; i < n; i++) {
        if (isPrime[i]) count++;
    }
    free(isPrime);
    return count;
}

js

/**
 * @param {number} n
 * @return {number}
 */
var countPrimes = function (n) {
  if (n < 2) return 0
  const isPrime = new Array(n).fill(true)
  isPrime[0] = 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
      }
    }
  }
  return isPrime.filter(Boolean).length
}

py

class Solution:
    def countPrimes(self, n: int) -> int:
        if n < 2:
            return 0
        is_prime = [True] * n
        is_prime[0] = is_prime[1] = False
        i = 2
        while i * i < n:
            if is_prime[i]:
                for j in range(i * i, n, i):
                    is_prime[j] = False
            i += 1
        return sum(is_prime)

• 时间复杂度：$O(n\log \log n)$，埃拉托斯特尼筛法的时间复杂度
• 空间复杂度：$O(n)$，布尔数组的大小

算法思路：

• 初始化布尔数组，所有数默认为质数
• 从 2 开始，将每个质数的倍数标记为非质数，从 $i^2$ 开始标记以避免重复