Java筛法求素数详解（埃拉托斯特尼筛法从入门到实战）

为什么使用筛法？

相比传统的逐个判断法（时间复杂度约为 O(n√n)），埃拉托斯特尼筛法的时间复杂度仅为 O(n log log n)，在处理大范围数据时优势明显。这也是为什么Java高效求素数常采用此方法。

Java实现步骤详解

下面我们一步步用 Java 实现筛法求素数：

1. 创建一个布尔数组 isPrime[0..n]，初始化为 true。
2. 将 isPrime[0] 和 isPrime[1] 设为 false（因为0和1不是素数）。
3. 从2开始遍历到 √n：
• 如果当前数 i 是素数（即 isPrime[i] == true），则将其所有倍数（从 i² 开始）标记为 false。
4. 遍历完成后，数组中值为 true 的索引即为素数。

完整Java代码示例

以下是一个完整的、可直接运行的 Java 程序，展示了如何使用筛法找出 1 到 100 之间的所有素数：

public class SieveOfEratosthenes {    public static void findPrimes(int n) {        // 创建布尔数组，初始值全为true        boolean[] isPrime = new boolean[n + 1];        for (int i = 0; i <= n; i++) {            isPrime[i] = true;        }        // 0和1不是素数        isPrime[0] = false;        isPrime[1] = false;        // 从2开始筛选        for (int i = 2; i * i <= n; i++) {            if (isPrime[i]) {                // 将i的所有倍数标记为非素数                for (int j = i * i; j <= n; j += i) {                    isPrime[j] = false;                }            }        }        // 输出所有素数        System.out.println("小于等于 " + n + " 的素数有：");        for (int i = 2; i <= n; i++) {            if (isPrime[i]) {                System.out.print(i + " ");            }        }        System.out.println();    }    public static void main(String[] args) {        findPrimes(100);    }}  

代码说明

在上述代码中：

• 我们使用 boolean[] isPrime 数组来记录每个数字是否为素数。
• 外层循环只需运行到 √n，因为大于 √n 的合数一定已被更小的因子筛除。
• 内层循环从 i * i 开始，因为小于 i * i 的倍数（如 2i, 3i...）已经被之前的素数筛掉了。

适合Java初学者的素数算法

这个算法逻辑清晰、结构简单，非常适合Java初学者素数算法的学习。通过理解筛法，你不仅能掌握一种高效算法，还能提升对数组和循环控制的理解。

总结

今天我们详细讲解了如何用 Java 实现埃拉托斯特尼筛法来高效求解素数。无论你是准备面试，还是学习算法基础，掌握Java筛法求素数都是非常有价值的技能。希望这篇教程能帮助你轻松入门！

提示：你可以尝试修改代码中的 n 值，观察不同范围内的素数结果，加深理解。