1. 问题定义

素数（质数）是指在大于 1 的自然数中，除了 1 和它本身以外不再有其他因数的数。常见的需求有两类：

  • 判定单个整数 n 是否为素数。
  • 筛选出区间 [1, n] 内的所有素数。

本文聚焦第二类问题的优化方法。

2. 单个判定：试除法

试除法是最基础的素数判定方法。对于整数 n，只需检查 2 到 √n 之间是否存在 n 的因子。

1
2
3
4
5
6
7
boolean isPrime(int n) {
    if (n < 2) return false;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) return false;
    }
    return true;
}

时间复杂度：O(√n)

若用此方法逐个判定 [1, n] 内的每个数，总复杂度为 O(n√n)，当 n 较大时不可接受。

3. 埃拉托斯特尼筛法（Sieve of Eratosthenes）

3.1 原理
埃筛的核心思想是：从 2 开始，从小到大遍历每个数，若该数未被标记为合数，则它是素数，然后将它的所有倍数标记为合数。遍历完成后，未被标记的数即为素数。

3.2 实现

1
2
3
4
5
6
7
8
9
10
11
12
boolean[] isComposite = new boolean[n + 1];
List<Integer> primes = new ArrayList<>();

for (int i = 2; i <= n; i++) {
    if (!isComposite[i]) {
        primes.add(i);
        // 从 i*i 开始标记，因为小于 i*i 的倍数已经被更小的素数标记过
        for (int j = i * i; j <= n; j += i) {
            isComposite[j] = true;
        }
    }
}

3.3 复杂度分析
时间复杂度：O(n log log n)，与调和级数相关，当 n 很大时接近线性。

空间复杂度：O(n)，需要布尔数组标记合数。

3.4 优缺点
优点：实现简单，常数较小，实际性能优秀。

缺点：存在重复标记（例如 6 会被 2 和 3 各标记一次），当 n 极大时仍可进一步优化。

4. 欧拉线性筛（Linear Sieve）

4.1 核心思想
线性筛保证每个合数只被其最小的质因子筛掉，从而将标记次数降至 O(n)，达到线性时间复杂度。

4.2 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
boolean[] isComposite = new boolean[n + 1];
List<Integer> primes = new ArrayList<>();

for (int i = 2; i <= n; i++) {
    if (!isComposite[i]) {
        primes.add(i);
    }
    // 用已收集的素数去筛掉合数 i * prime
    for (int j = 0; j < primes.size() && i * primes.get(j) <= n; j++) {
        isComposite[i * primes.get(j)] = true;
        // 若 prime 能整除 i，则 prime 是 i 的最小质因子，
        // 用 i * nextPrime 会被更小的质因子筛掉，所以必须 break
        if (i % primes.get(j) == 0) break;
    }
}

4.3 复杂度与正确性
时间复杂度：严格 O(n)，每个合数仅被访问一次。

正确性依赖于 if (i % primes.get(j) == 0) break; 这行代码。该条件确保 primes[j] 是 i 的最小质因子，进而保证 i * primes[j] 的最小质因子也是 primes[j]。若继续使用后续更大的素数，则最小质因子将不再是当前素数，会导致后续被重复标记。

4.4 性能对比（n = 10^7 量级）
方法 时间复杂度 实际耗时（估算）
逐个试除 O(n√n) 数十分钟
埃筛 O(n log log n) 约 1~2 秒
线性筛 O(n) 约 1 秒
线性筛虽然在渐进意义上更优，但在现代机器上，埃筛的常数更小，两者实际运行时间往往相差不大。然而线性筛的结构更适合扩展，比如同时求积性函数的值。

5. 优化技巧与工程实践

使用 BitSet 压缩空间：将布尔数组替换为 java.util.BitSet，空间可缩减至原来的 1/8。

只筛奇数：偶数中除 2 外均为合数，可单独处理 2，然后仅对奇数进行筛选，空间和时间均减半。

分段筛：当 n 极大（如 10^9 以上）且无法一次性分配数组时，可将区间分块，每块分别用埃筛处理，对外部素数表进行筛选。

6. 适用场景总结

判定单个整数：直接使用 O(√n) 的试除法。

筛选中等规模素数（n ≤ 10^7）：埃筛实现简单，推荐使用。

对性能要求苛刻或需同时计算数论函数：采用线性筛。

内存受限或 n 极大：考虑分段筛或位图压缩。