Fork me on GitHub
Hike News
Hike News

01/80 统计素数个数-暴力算法

0 - 算法, 0.2 - 80 道基础算法 本文总阅读量次

题目描述

给定一个整数数组，统计其中素数（质数）的个数。
素数定义：在一个大于 1 的自然数中，除了 1 和它本身以外不再有其他因数的自然数。

核心思路

1. 暴力判定法

对于每一个数字 n，我们从 2 开始尝试除到 n-1。如果期间能被整除，说明不是素数。

2. 优化逻辑：$\sqrt{n}$ 法

其实我们不需要一直除到 n-1。

  • 如果 $n = a \times b$，那么 $a$ 和 $b$ 中至少有一个会小于或等于 $\sqrt{n}$。
  • 例如判断 16 是否为素数，我们只需要检查 2、3、4。因为如果 4 以后还有因子（如 8），那么必然对应一个小于 4 的因子（如 2），而我们在检查到 2 时就已经发现了。
  • 结论：只需要遍历到 sqrt(n) 即可将单次判定的复杂度从 $O(n)$ 降低到 $O(\sqrt{n})$。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
 * 判断一个数是否为素数
 */
fun isPrime(n: Int): Boolean {
    // 小于等于 1 的数不是素数
    if (n <= 1) return false
    
    // 基础优化：从 2 遍历到 sqrt(n)
    var i = 2
    while (i * i <= n) {
        if (n % i == 0) {
            return false
        }
        i++
    }
    return true
}

/**
 * 统计数组中素数的个数
 */
fun countPrimesInArray(arr: IntArray): Int {
    var count = 0
    for (num in arr) {
        if (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(N \cdot \sqrt{M})$。
    • 其中 $N$ 为数组长度，$M$ 为数组中数值的大小。
    • 对于数组中的每个元素，我们执行一次判定，判定耗时 $O(\sqrt{M})$。
  • 空间复杂度：$O(1)$。只使用了常数个变量进行计数和迭代。

进阶思考：如果要统计 0 到 N 之间的所有素数？

对于大规模范围内的素数统计（例如统计 100 万以内的素数个数），暴力算法会显得力不从心。此时可以采用 埃拉托斯特尼筛法（Sieve of Eratosthenes）：

  1. 建立一个布尔数组 isPrime，初始全部设为 true。
  2. 从 2 开始，如果是素数，则将其所有的倍数（2x, 3x…）标记为 false。
  3. 这样每个合数只会被标记几次，时间复杂度可以大幅优化至 $O(N \log \log N)$。
0 - 算法, 0.2 - 80 道基础算法