02/80 统计素数个数-埃氏筛选法

题目描述

给定一个正整数 $n$ 或一个整数数组，统计其中素数的个数。
对于大规模范围内的素数统计，暴力判定法（$O(N\sqrt{N})$）效率较低。本篇介绍经典的 埃拉托斯特尼筛法（Sieve of Eratosthenes）。

---

核心思路

埃氏筛法的核心思想是：“素数的倍数一定是合数”。

1. 初始化：建立一个长度为 max + 1 的布尔数组 isPrime，初始全部设为 true。将 0 和 1 设为 false。
2. 筛选：从 2 开始遍历到 sqrt(max)：
   • 如果当前数字 i 是素数，则将其所有的倍数（$2i, 3i, 4i \dots$）标记为 false（非素数）。
3. 优化点：
   • 从 $i^2$ 开始标记：在筛选素数 i 的倍数时，小于 $i^2$ 的倍数（如 $2i, 3i \dots$）其实已经被之前的素数（$2, 3 \dots$）标记过了。因此直接从 $i \times i$ 开始标记可以减少重复操作。
   • 遍历边界：只需遍历到 sqrt(max) 即可完成所有合数的标记。

---

代码实现 (Kotlin)

import kotlin.math.sqrt

/**
 * 使用埃氏筛法统计数组中的素数个数
 */
fun countPrimesInArray(arr: IntArray): Int {
    if (arr.isEmpty()) return 0

    // 1. 找到数组中的最大值，确定筛的大小
    val maxVal = arr.maxOrNull() ?: 0
    if (maxVal < 2) return 0

    // 2. 预处理：构建埃氏筛
    val isPrime = BooleanArray(maxVal + 1) { true }
    isPrime[0] = false
    isPrime[1] = false

    val limit = sqrt(maxVal.toDouble()).toInt()
    for (i in 2..limit) {
        if (isPrime[i]) {
            // 从 i*i 开始标记，步长为 i
            for (j in i * i..maxVal step i) {
                isPrime[j] = false
            }
        }
    }

    // 3. 查表统计结果
    var count = 0
    for (num in arr) {
        if (num >= 0 && isPrime[num]) {
            count++
        }
    }

    return count
}

fun main() {
    val arr = intArrayOf(2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15)
    // 预期结果：2, 3, 5, 7, 11, 13 共 6 个
    println("数组中素数的个数为: ${countPrimesInArray(arr)}")
}

---

复杂度分析

• 时间复杂度：$O(M \log \log M + N)$。
  • $M$ 是数组中的最大值。构建筛子的复杂度是数学上证明的 $O(M \log \log M)$，接近线性。
  • $N$ 是数组长度，用于最后的遍历统计。
• 空间复杂度：$O(M)$。需要一个长度为 $M+1$ 的布尔数组来存储筛选状态。

---

算法对比与总结

特性	暴力判定法	埃氏筛法
时间复杂度	$O(N \cdot \sqrt{M})$	$O(M \log \log M)$
空间复杂度	$O(1)$	$O(M)$
适用场景	数组元素较少，但数值极大	数组元素多，或需要频繁查询某一范围内的素数

技巧提示：如果题目是要求“统计 $n$ 以内的素数个数”，埃氏筛法是面试中的标准答案。如果是针对“数组中”的素数且数组很大，先求最大值并建筛（查表法）是最高效的工业实践。