每日算法 — 使用java实现埃拉托斯特尼筛法：高效素数生成

问题描述

素数（质数）是大于1的自然数中，除了1和它本身以外不再有其他因数的数。素数在密码学、哈希算法、随机数生成等领域有广泛应用。给定一个正整数 n，如何高效地找出所有小于等于 n 的素数？

埃拉托斯特尼筛法（Sieve of Eratosthenes）是最经典、最高效的素数生成算法之一，由古希腊数学家埃拉托斯特尼发明。

算法思路

基本思想

1. 创建一个布尔数组 isPrime[0..n]，初始时假设所有数都是素数
2. 从第一个素数2开始，将2的所有倍数标记为合数
3. 找到下一个未被标记的数，它也是素数，将其所有倍数标记为合数
4. 重复步骤3，直到遍历到 √n

优化策略

1. 只需筛到 √n：如果 n 是合数，它必有一个不大于 √n 的因数
2. 从 i² 开始标记：对于素数 i，i×2, i×3, ..., i×(i-1) 已被更小的素数标记过
3. 跳过偶数：除了2以外，所有偶数都不是素数，可以只处理奇数
4. 位图压缩：使用位运算压缩存储空间

Java实现

基础版筛法

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

public class SieveOfEratosthenes {
    /**
     * 基础版埃拉托斯特尼筛法
     * 时间复杂度：O(n log log n)
     * 空间复杂度：O(n)
     *
     * @param n 上限
     * @return 所有小于等于n的素数列表
     */
    public static List<Integer> sieveBasic(int n) {
        if (n < 2) {
            return new ArrayList<>();
        }

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

        for (int i = 2; i <= n; i++) {
            if (!isComposite[i]) {
                primes.add(i);
                // 将i的所有倍数标记为合数
                // 优化：从i*i开始，因为i*2, i*3, ... i*(i-1)已被更小的素数标记
                if ((long) i * i <= n) {
                    for (int j = i * i; j <= n; j += i) {
                        isComposite[j] = true;
                    }
                }
            }
        }

        return primes;
    }

    /**
     * 优化版：只处理奇数，节省一半空间
     */
    public static List<Integer> sieveOptimized(int n) {
        if (n < 2) {
            return new ArrayList<>();
        }

        List<Integer> primes = new ArrayList<>();
        primes.add(2);

        if (n < 3) {
            return primes;
        }

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

        return primes;
    }

    /**
     * 线性筛（欧拉筛）：每个合数只被其最小质因数筛一次
     * 时间复杂度：O(n)
     */
    public static List<Integer> linearSieve(int n) {
        if (n < 2) {
            return new ArrayList<>();
        }

        boolean[] isComposite = new boolean[n + 1];
        List<Integer> primes = new ArrayList<>();

        for (int i = 2; i <= n; i++) {
            if (!isComposite[i]) {
                primes.add(i);
            }
            for (int p : primes) {
                if ((long) i * p > n) {
                    break;
                }
                isComposite[i * p] = true;
                if (i % p == 0) {
                    // p是i的最小质因数，保证每个合数只被筛一次
                    break;
                }
            }
        }

        return primes;
    }

    /**
     * 判断单个数是否为素数（基于预处理的筛法结果）
     */
    public static boolean isPrime(int n, boolean[] sieve) {
        if (n < 2 || n >= sieve.length) {
            return false;
        }
        return !sieve[n];
    }

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

        System.out.println("基础筛法（n=" + n + "）：" + sieveBasic(n));
        System.out.println("优化筛法（n=" + n + "）：" + sieveOptimized(n));
        System.out.println("线性筛法（n=" + n + "）：" + linearSieve(n));

        // 性能测试
        int testN = 10_000_000;
        long start = System.currentTimeMillis();
        List<Integer> largePrimes = sieveOptimized(testN);
        long end = System.currentTimeMillis();
        System.out.println("\n优化筛法生成 " + testN + " 以内素数：" + largePrimes.size() + " 个");
        System.out.println("耗时：" + (end - start) + " ms");
    }
}

扩展：素数计数函数与素性测试

public class PrimeUtils {
    /**
     * 快速判断大数是否为素数（确定性Miller-Rabin，适用于int范围）
     */
    public static boolean isPrimeDeterministic(int n) {
        if (n < 2) return false;
        if (n == 2 || n == 3) return true;
        if (n % 2 == 0) return false;

        // 将n-1分解为d * 2^s
        int d = n - 1;
        int s = 0;
        while (d % 2 == 0) {
            d /= 2;
            s++;
        }

        // 对于int范围，测试基{2, 7, 61}足够
        int[] bases = {2, 7, 61};
        for (int a : bases) {
            if (a >= n) continue;
            long x = modPow(a, d, n);
            if (x == 1 || x == n - 1) continue;

            boolean continueOuter = false;
            for (int r = 1; r < s; r++) {
                x = (x * x) % n;
                if (x == n - 1) {
                    continueOuter = true;
                    break;
                }
            }
            if (continueOuter) continue;
            return false;
        }
        return true;
    }

    private static long modPow(long base, long exp, long mod) {
        long result = 1;
        base %= mod;
        while (exp > 0) {
            if ((exp & 1) == 1) {
                result = (result * base) % mod;
            }
            base = (base * base) % mod;
            exp >>= 1;
        }
        return result;
    }
}

复杂度分析

实际应用

1. 密码学：RSA算法需要生成大素数，筛法用于快速排除合数候选
2. 哈希表：素数大小的哈希表可以减少冲突
3. 随机数生成：梅森旋转等算法需要素数参数
4. 竞赛编程：快速预处理素数表，支持O(1)素性查询

总结

埃拉托斯特尼筛法是数论算法的基础，其核心思想是用”空间换时间”，通过预处理将素性判断从O(√n)降到O(1)。线性筛进一步优化到严格的O(n)，是竞赛编程和工程实践中的常用技巧。理解筛法的原理，对掌握数论算法和优化思想至关重要。