每日算法 — 使用java实现埃拉托斯特尼筛：素数筛法与线性筛优化

引言

素数（质数）是数论中最基础也最重要的概念之一。埃拉托斯特尼筛法（Sieve of Eratosthenes）是古希腊数学家埃拉托斯特尼发明的一种高效筛选素数的算法，至今仍是最经典的素数生成方法。本文将用Java实现埃拉托斯特尼筛及其多种优化版本，包括线性筛（欧拉筛），帮助读者理解素数分布规律与算法优化的艺术。

算法原理

埃拉托斯特尼筛法的核心思想：

1. 创建一个从 2 到 n 的连续整数列表
2. 从第一个素数 2 开始，将所有 2 的倍数标记为合数
3. 找到下一个未被标记的数，它一定是素数，然后将其所有倍数标记为合数
4. 重复步骤 3，直到遍历完所有数

关键洞察：只需筛选到 √n 即可，因为如果 n 有一个大于 √n 的因子，它必然对应一个小于 √n 的因子。

基础实现

import java.util.Arrays;
import java.util.ArrayList;
import java.util.List;

/**
 * 埃拉托斯特尼筛法及其优化实现
 */
public class SieveOfEratosthenes {

    /**
     * 基础版埃拉托斯特尼筛
     * 时间复杂度: O(n log log n)
     * 空间复杂度: O(n)
     */
    public static List<Integer> sieveBasic(int n) {
        boolean[] isComposite = new boolean[n + 1]; // false表示素数，true表示合数
        List<Integer> primes = new ArrayList<>();

        for (int i = 2; i <= n; i++) {
            if (!isComposite[i]) {
                primes.add(i); // i是素数
                // 标记所有i的倍数为合数
                for (int j = i * 2; j <= n; j += i) {
                    isComposite[j] = true;
                }
            }
        }

        return primes;
    }

优化一：只筛到平方根

    /**
     * 优化1：外层循环只需到 sqrt(n)
     * 原理：如果n是合数，它必有一个不大于sqrt(n)的因子
     * 时间复杂度仍为 O(n log log n)，但常数更小
     */
    public static List<Integer> sieveSqrtOptimization(int n) {
        boolean[] isComposite = new boolean[n + 1];
        List<Integer> primes = new ArrayList<>();

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

        // 收集所有素数
        for (int i = 2; i <= n; i++) {
            if (!isComposite[i]) {
                primes.add(i);
            }
        }

        return primes;
    }

优化二：从i*i开始标记

    /**
     * 优化2：内层循环从 i*i 开始（已在优化1中包含）
     * 原因：对于素数p，p*2, p*3, ..., p*(p-1) 都含有比p小的因子
     *      因此它们已经被更小的素数标记过了
     *
     * 例如：当 i=5 时，10, 15, 20 已经被 2 和 3 标记过
     *       只需从 25 开始标记
     */
    public static List<Integer> sieveWithPrimesOnly(int n) {
        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 <= n 时才需要标记（防止溢出）
                if ((long) i * i <= n) {
                    for (int j = i * i; j <= n; j += i) {
                        isComposite[j] = true;
                    }
                }
            }
        }

        return primes;
    }

优化三：排除偶数（位运算压缩）

    /**
     * 优化3：排除偶数（除2外所有偶数都不是素数）
     * 空间减半，只需标记奇数
     * 使用位数组进一步压缩空间
     */
    public static List<Integer> sieveOddOnly(int n) {
        if (n < 2) return new ArrayList<>();

        List<Integer> primes = new ArrayList<>();
        primes.add(2); // 2是唯一的偶素数

        if (n == 2) return primes;

        // isComposite[i] 对应奇数 2*i+1 是否为合数
        // 例如 i=0 -> 1, i=1 -> 3, i=2 -> 5
        // 实际上我们只需要从3开始，所以用 (n-1)/2 个元素
        int size = (n - 1) / 2; // 3, 5, 7, ..., n(或n-1)
        boolean[] isComposite = new boolean[size];

        for (int i = 0; i < size; i++) {
            if (!isComposite[i]) {
                int prime = 2 * i + 3; // 对应的奇数素数
                primes.add(prime);

                // prime * prime = (2i+3)^2 = 4i^2 + 12i + 9
                // 对应索引: (p*p - 3) / 2
                long start = (long) prime * prime;
                if (start > n) continue;

                // 标记 prime 的所有奇数倍数
                // 从 prime*prime 开始，步长为 2*prime（只跳奇数倍）
                for (long j = start; j <= n; j += 2L * prime) {
                    isComposite[(int) (j - 3) / 2] = true;
                }
            }
        }

        return primes;
    }

优化四：线性筛（欧拉筛）

线性筛是埃拉托斯特尼筛的终极优化版本，每个合数只被其最小质因子筛除一次，时间复杂度严格为 O(n)。

    /**
     * 线性筛（欧拉筛）：每个合数只被最小质因子标记一次
     * 时间复杂度: 严格 O(n)
     * 空间复杂度: O(n)
     *
     * 核心思想：
     * 1. 维护一个素数列表 primes
     * 2. 遍历每个数 i，用已知的素数去标记 i 的倍数
     * 3. 当素数 p 能整除 i 时停止，保证每个合数只被最小质因子筛除
     */
    public static List<Integer> linearSieve(int n) {
        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 的倍数
            for (int j = 0; j < primes.size() && i * primes.get(j) <= n; j++) {
                isComposite[i * primes.get(j)] = true;

                // 关键优化：如果 primes[j] 是 i 的最小质因子，则停止
                // 这保证了每个合数只被其最小质因子筛除一次
                if (i % primes.get(j) == 0) {
                    break;
                }
            }
        }

        return primes;
    }

完整代码与性能对比

    /**
     * 计算素数个数（用于快速验证）
     */
    public static int countPrimes(int n) {
        return linearSieve(n).size();
    }

    /**
     * 获取第k个素数
     */
    public static int kthPrime(int k) {
        // 素数定理：第n个素数约等于 n * ln(n)
        // 为了安全，取上限为 k * (ln(k) + 2)
        int upperBound;
        if (k < 6) {
            upperBound = 15;
        } else {
            upperBound = (int) (k * (Math.log(k) + 2)) + 10;
        }
        List<Integer> primes = linearSieve(upperBound);
        return primes.get(k - 1);
    }

    /**
     * 素性测试：判断单个数是否为素数（利用预处理的素数表）
     */
    public static boolean isPrime(int n, List<Integer> primes) {
        if (n < 2) return false;
        for (int p : primes) {
            if ((long) p * p > n) break;
            if (n % p == 0) return n == p;
        }
        return true;
    }

    /**
     * 主程序：测试所有版本并对比性能
     */
    public static void main(String[] args) {
        int n = 10000000; // 一千万

        System.out.println("=== 埃拉托斯特尼筛法性能测试 ===");
        System.out.println("范围: 1 ~ " + n);
        System.out.println();

        // 基础版
        long start = System.currentTimeMillis();
        List<Integer> primesBasic = sieveBasic(n);
        long timeBasic = System.currentTimeMillis() - start;
        System.out.println("基础版: " + primesBasic.size() + " 个素数, 耗时 " + timeBasic + "ms");

        // 平方根优化
        start = System.currentTimeMillis();
        List<Integer> primesSqrt = sieveSqrtOptimization(n);
        long timeSqrt = System.currentTimeMillis() - start;
        System.out.println("Sqrt优化: " + primesSqrt.size() + " 个素数, 耗时 " + timeSqrt + "ms");

        // 奇数优化
        start = System.currentTimeMillis();
        List<Integer> primesOdd = sieveOddOnly(n);
        long timeOdd = System.currentTimeMillis() - start;
        System.out.println("奇数优化: " + primesOdd.size() + " 个素数, 耗时 " + timeOdd + "ms");

        // 线性筛
        start = System.currentTimeMillis();
        List<Integer> primesLinear = linearSieve(n);
        long timeLinear = System.currentTimeMillis() - start;
        System.out.println("线性筛: " + primesLinear.size() + " 个素数, 耗时 " + timeLinear + "ms");

        // 验证结果一致性
        System.out.println();
        System.out.println("结果一致性验证:");
        System.out.println("基础版 == 线性筛: " + primesBasic.equals(primesLinear));

        // 输出前20个素数
        System.out.println();
        System.out.println("前20个素数: " + primesLinear.subList(0, 20));

        // 输出第10000个素数
        System.out.println("第10000个素数: " + kthPrime(10000));

        // 区间素数计数（素数定理验证）
        int count = countPrimes(1000000);
        double approx = 1000000.0 / Math.log(1000000);
        System.out.println();
        System.out.println("1~1000000 素数个数: " + count);
        System.out.println("素数定理近似值: " + String.format("%.2f", approx));
        System.out.println("误差: " + String.format("%.4f%%", Math.abs(count - approx) / count * 100));
    }
}

复杂度分析

数学推导：埃拉托斯特尼筛的时间复杂度为 O(n log log n)，这是因为：

$$
\sum_{p \leq n, p \text{ prime}} \frac{n}{p} = n \sum_{p \leq n} \frac{1}{p} \approx n \log \log n
$$

其中利用了素数倒数和的性质。

扩展应用

1. 区间筛：给定区间 [L, R]，求其中的素数。先用线性筛求出 [2, √R] 的素数，再用这些素数去标记区间内的合数
2. 欧拉函数表：利用线性筛同时计算每个数的最小质因子和欧拉函数值 φ(n)
3. 莫比乌斯函数表：类似地，可在线性筛过程中计算莫比乌斯函数 μ(n)
4. 素因子分解预处理：记录每个数的最小质因子，实现 O(log n) 的分解

    /**
     * 扩展：线性筛同时计算最小质因子和欧拉函数
     */
    public static void sieveWithEulerPhi(int n) {
        boolean[] isComposite = new boolean[n + 1];
        int[] minPrime = new int[n + 1]; // 最小质因子
        int[] phi = new int[n + 1];      // 欧拉函数
        List<Integer> primes = new ArrayList<>();

        phi[1] = 1;

        for (int i = 2; i <= n; i++) {
            if (!isComposite[i]) {
                primes.add(i);
                minPrime[i] = i;
                phi[i] = i - 1; // 素数的欧拉函数 = p - 1
            }

            for (int j = 0; j < primes.size() && i * primes.get(j) <= n; j++) {
                int p = primes.get(j);
                isComposite[i * p] = true;
                minPrime[i * p] = p;

                if (i % p == 0) {
                    // p 是 i 的最小质因子
                    phi[i * p] = phi[i] * p;
                    break;
                } else {
                    phi[i * p] = phi[i] * (p - 1);
                }
            }
        }

        // 输出部分结果验证
        System.out.println("\n欧拉函数值（部分）:");
        for (int i = 1; i <= 20; i++) {
            System.out.println("φ(" + i + ") = " + phi[i]);
        }
    }

总结

埃拉托斯特尼筛法从古希腊流传至今，其优化过程本身就是算法设计的典范。基础筛法利用素数的倍数标记合数，时间复杂度为 O(n log log n)；线性筛通过”每个合数只被最小质因子筛除”的精妙设计，将复杂度降到严格的 O(n)。掌握这些筛法不仅能高效解决素数相关问题，更能培养对算法复杂度优化的直觉。在竞赛编程和实际工程中，线性筛是处理数论问题的必备工具。