每日算法 — 使用java实现素数筛：埃氏筛与欧拉筛的高效质数生成

素数（质数）是数论的基础，而高效地筛选素数是许多算法的基石。本文深入讲解两种经典的素数筛法——埃拉托斯特尼筛（埃氏筛）和欧拉筛（线性筛），分析它们的原理差异，并给出完整的Java实现与性能对比。

问题背景

素数定义：大于1的自然数，除了1和它本身外，不能被其他自然数整除。

素数筛问题：给定上限 $N$，找出 $[2, N]$ 范围内的所有素数。

朴素做法：对每个数 $i$，检查 $2$ 到 $\sqrt{i}$ 是否能整除它。时间复杂度 $O(N\sqrt{N})$，当 $N = 10^7$ 时速度极慢。

埃拉托斯特尼筛（埃氏筛）

核心思想

埃氏筛基于一个简单事实：如果 $p$ 是素数，那么 $2p, 3p, 4p, …$ 都是合数。

算法步骤：
1. 初始化一个布尔数组，假设所有数都是素数
2. 从2开始遍历，如果当前数 $i$ 是素数，则将 $i$ 的所有倍数标记为合数
3. 最终未被标记的数即为素数

时间复杂度分析

$$O(N \log \log N)$$

推导：标记操作的次数约为 $N/2 + N/3 + N/5 + N/7 + … = N \sum_{p \leq N} 1/p$，而素数倒数和收敛于 $\log \log N$。

Java实现

import java.util.*;

/**
 * 埃拉托斯特尼筛（埃氏筛）
 * 时间复杂度 O(N log log N)，空间复杂度 O(N)
 */
public class SieveOfEratosthenes {

    /**
     * 基础埃氏筛：找出 [2, n] 范围内的所有素数
     */
    public List<Integer> sieve(int n) {
        if (n < 2) {
            return new ArrayList<>();
        }

        boolean[] isComposite = new boolean[n + 1]; // false 表示素数，true 表示合数
        List<Integer> primes = new ArrayList<>();

        for (int i = 2; i <= n; i++) {
            if (!isComposite[i]) {
                // i 是素数
                primes.add(i);

                // 标记 i 的所有倍数为合数
                // 注意：从 i*i 开始即可，因为更小的倍数已经被更小的素数标记过了
                if ((long) i * i <= n) {
                    for (int j = i * i; j <= n; j += i) {
                        isComposite[j] = true;
                    }
                }
            }
        }

        return primes;
    }

    /**
     * 优化的埃氏筛：仅处理奇数，节省一半空间
     */
    public List<Integer> sieveOptimized(int n) {
        if (n < 2) return new ArrayList<>();

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

        if (n < 3) return primes;

        // 只存储奇数：索引 i 对应数字 2i+3
        int size = (n - 1) / 2;
        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 开始标记，步长为 2*prime（只标记奇数倍数）
                long start = (long) prime * prime;
                if (start <= n) {
                    int startIdx = (int) ((start - 3) / 2);
                    for (int j = startIdx; j < size; j += prime) {
                        isComposite[j] = true;
                    }
                }
            }
        }

        return primes;
    }

    /**
     * 扩展1：计算每个数的最小质因子（用于后续质因数分解）
     */
    public int[] minPrimeFactor(int n) {
        int[] mpf = new int[n + 1];

        for (int i = 2; i <= n; i++) {
            if (mpf[i] == 0) { // i 是素数
                mpf[i] = i;
                if ((long) i * i <= n) {
                    for (int j = i * i; j <= n; j += i) {
                        if (mpf[j] == 0) {
                            mpf[j] = i;
                        }
                    }
                }
            }
        }

        return mpf;
    }

    /**
     * 扩展2：利用最小质因子数组进行质因数分解
     */
    public List<int[]> primeFactorization(int x, int[] mpf) {
        List<int[]> factors = new ArrayList<>();

        while (x > 1) {
            int p = mpf[x];
            int count = 0;
            while (x % p == 0) {
                x /= p;
                count++;
            }
            factors.add(new int[]{p, count});
        }

        return factors;
    }

    /**
     * 扩展3：计算区间 [l, r] 内的素数（分段筛）
     * 适用于 r 很大但 r-l 不大的情况
     */
    public List<Integer> segmentedSieve(long l, long r) {
        int limit = (int) Math.sqrt(r) + 1;
        List<Integer> basePrimes = sieve(limit);

        int segmentSize = (int) (r - l + 1);
        boolean[] isComposite = new boolean[segmentSize];

        for (int p : basePrimes) {
            // 找到区间内 p 的第一个倍数
            long start = Math.max((long) p * p, ((l + p - 1) / p) * p);
            for (long j = start; j <= r; j += p) {
                isComposite[(int) (j - l)] = true;
            }
        }

        List<Integer> primes = new ArrayList<>();
        for (int i = 0; i < segmentSize; i++) {
            if (!isComposite[i] && (l + i) > 1) {
                primes.add((int) (l + i));
            }
        }

        return primes;
    }

    public static void main(String[] args) {
        SieveOfEratosthenes sieve = new SieveOfEratosthenes();
        int n = 100;

        System.out.println("=== 埃氏筛（基础版） ===");
        List<Integer> primes = sieve.sieve(n);
        System.out.println("2~" + n + " 的素数: " + primes);
        System.out.println("素数个数: " + primes.size());

        System.out.println("\\n=== 埃氏筛（奇数优化版） ===");
        List<Integer> primesOpt = sieve.sieveOptimized(n);
        System.out.println("2~" + n + " 的素数: " + primesOpt);

        // 质因数分解演示
        System.out.println("\\n=== 质因数分解演示 ===");
        int[] mpf = sieve.minPrimeFactor(100);
        int[] testNumbers = {60, 84, 97, 100};
        for (int num : testNumbers) {
            List<int[]> factors = sieve.primeFactorization(num, mpf);
            StringBuilder sb = new StringBuilder(num + " = ");
            for (int i = 0; i < factors.size(); i++) {
                int[] f = factors.get(i);
                sb.append(f[0]).append("^").append(f[1]);
                if (i < factors.size() - 1) sb.append(" * ");
            }
            System.out.println("  " + sb);
        }

        // 分段筛演示
        System.out.println("\\n=== 分段筛演示 ===");
        List<Integer> segPrimes = sieve.segmentedSieve(1000, 1050);
        System.out.println("1000~1050 的素数: " + segPrimes);
    }
}

欧拉筛（线性筛）

核心思想

埃氏筛的缺陷在于同一个合数会被多个素数重复标记。例如 30 = 2×15 = 3×10 = 5×6，会被标记3次。

欧拉筛的关键优化：每个合数只被它的最小质因子标记一次。

具体规则：
– 对于每个数 $i$，遍历已知素数表中的素数 $p$
– 标记 $i \times p$ 为合数
– 如果 $i$ 能被 $p$ 整除，则停止遍历（保证每个合数只被最小质因子标记）

时间复杂度：O(N)，每个数仅被标记一次

Java实现

import java.util.*;

/**
 * 欧拉筛（线性筛）
 * 时间复杂度 O(N)，空间复杂度 O(N)
 * 每个合数仅被其最小质因子标记一次
 */
public class EulerSieve {

    /**
     * 线性筛：同时得到素数表和每个数的最小质因子
     */
    public SieveResult linearSieve(int n) {
        if (n < 2) {
            return new SieveResult(new ArrayList<>(), new int[0]);
        }

        boolean[] isComposite = new boolean[n + 1];
        int[] minPrime = new int[n + 1]; // 最小质因子
        List<Integer> primes = new ArrayList<>();

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

            // 用当前已知的素数标记合数
            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;

                // 核心优化：如果 i 能被 p 整除，则 p 是 i 的最小质因子
                // 此时 i*p 的最小质因子也是 p，应停止，避免重复标记
                if (i % p == 0) {
                    break;
                }
            }
        }

        return new SieveResult(primes, minPrime);
    }

    static class SieveResult {
        List<Integer> primes;
        int[] minPrime;

        SieveResult(List<Integer> primes, int[] minPrime) {
            this.primes = primes;
            this.minPrime = minPrime;
        }
    }

    /**
     * 利用线性筛的结果快速进行质因数分解
     */
    public Map<Integer, Integer> factorize(int x, int[] minPrime) {
        Map<Integer, Integer> factors = new LinkedHashMap<>();

        while (x > 1) {
            int p = minPrime[x];
            factors.merge(p, 1, Integer::sum);
            x /= p;
        }

        return factors;
    }

    /**
     * 计算欧拉函数 phi(n)：小于等于n且与n互质的正整数的个数
     * 利用线性筛可以 O(N) 计算 1~N 的所有欧拉函数值
     */
    public int[] eulerTotient(int n) {
        int[] phi = new int[n + 1];
        boolean[] isComposite = new boolean[n + 1];
        List<Integer> primes = new ArrayList<>();

        phi[1] = 1;

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

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

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

        return phi;
    }

    /**
     * 计算莫比乌斯函数 mu(n)
     * mu(1)=1，若n有平方因子则mu(n)=0，否则mu(n)=(-1)^k（k为不同质因子个数）
     */
    public int[] mobiusFunction(int n) {
        int[] mu = new int[n + 1];
        boolean[] isComposite = new boolean[n + 1];
        List<Integer> primes = new ArrayList<>();

        mu[1] = 1;

        for (int i = 2; i <= n; i++) {
            if (!isComposite[i]) {
                primes.add(i);
                mu[i] = -1; // 素数有1个质因子
            }

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

                if (i % p == 0) {
                    // p^2 是 i*p 的因子
                    mu[i * p] = 0;
                    break;
                } else {
                    mu[i * p] = -mu[i];
                }
            }
        }

        return mu;
    }

    public static void main(String[] args) {
        EulerSieve sieve = new EulerSieve();
        int n = 100;

        System.out.println("=== 欧拉筛（线性筛） ===");
        SieveResult result = sieve.linearSieve(n);
        System.out.println("2~" + n + " 的素数: " + result.primes);
        System.out.println("素数个数: " + result.primes.size());

        // 质因数分解
        System.out.println("\\n=== 快速质因数分解 ===");
        int[] testNumbers = {60, 84, 100};
        for (int num : testNumbers) {
            Map<Integer, Integer> factors = sieve.factorize(num, result.minPrime);
            System.out.println("  " + num + " = " + factors);
        }

        // 欧拉函数
        System.out.println("\\n=== 欧拉函数 phi(n) ===");
        int[] phi = sieve.eulerTotient(30);
        System.out.print("  n:    ");
        for (int i = 1; i <= 30; i++) System.out.printf("%3d", i);
        System.out.print("\\n  phi:  ");
        for (int i = 1; i <= 30; i++) System.out.printf("%3d", phi[i]);
        System.out.println();

        // 莫比乌斯函数
        System.out.println("\\n=== 莫比乌斯函数 mu(n) ===");
        int[] mu = sieve.mobiusFunction(30);
        System.out.print("  n:   ");
        for (int i = 1; i <= 30; i++) System.out.printf("%3d", i);
        System.out.print("\\n  mu:  ");
        for (int i = 1; i <= 30; i++) System.out.printf("%3d", mu[i]);
        System.out.println();
    }
}

两种筛法对比

性能测试

public void benchmark() {
    int[] testSizes = {100000, 1000000, 10000000};

    for (int n : testSizes) {
        System.out.println("\\nN = " + n);

        long start1 = System.currentTimeMillis();
        new SieveOfEratosthenes().sieve(n);
        long time1 = System.currentTimeMillis() - start1;
        System.out.println("  埃氏筛: " + time1 + "ms");

        long start2 = System.currentTimeMillis();
        new EulerSieve().linearSieve(n);
        long time2 = System.currentTimeMillis() - start2;
        System.out.println("  欧拉筛: " + time2 + "ms");
    }
}

应用场景

素数筛是许多高级算法的基础：
– 密码学：RSA等加密算法依赖大素数
– 哈希表：选择素数作为表大小可减少冲突
– 数论问题：GCD、LCM、同余方程等
– 组合数学：与欧拉函数、莫比乌斯函数密切相关

掌握埃氏筛和欧拉筛，是深入数论算法的第一步。