本文是 Java 面向对象程序设计课程的课后作业，完整覆盖素数判断的基础方法与核心的埃拉托斯特尼筛法。重点讲解了素数生成的可视化遍历过程，用分步表格和可运行代码带你彻底搞懂这个经典算法。

一、素数的基本定义

素数（Prime Number），又称质数，是指在大于 1 的自然数中，除了 1 和它本身以外不再有其他因数的自然数。

• 最小的素数是 2（唯一的偶素数）
• 大于 2 的所有偶数都不是素数
• 素数有无穷多个（欧几里得《几何原本》已证明）
• 应用领域：密码学（RSA 加密）、哈希算法、数论研究等

二、基础：单个素数判断的逐步优化

在学习批量生成素数的筛法之前，我们先从最基础的单个素数判断开始，理解算法优化的思想。

2.1 最原始：暴力遍历法

思路：对于数 n，检查从 2 到 n-1 的所有整数是否能整除它。

public static boolean isPrimeBasic(int n) {
    if (n <= 1) return false;
    for (int i = 2; i < n; i++) {
        if (n % i == 0) return false;
    }
    return true;
}

• 时间复杂度：O(n)
• 缺点：效率极低，n=100 万时需要循环近百万次

2.2 第一次优化：平方根优化

数学原理：如果 n 是合数，必然存在因数 a 和 b=n/a，其中至少有一个 ≤ √n。因此只需检查到 √n 即可。

public static boolean isPrimeSqrt(int n) {
    if (n <= 1) return false;
    for (int i = 2; i <= Math.sqrt(n); i++) {
        if (n % i == 0) return false;
    }
    return true;
}

• 时间复杂度：O(√n)
• 优化效果：n=100 万时，循环次数从 999999 次减少到 1000 次

2.3 第二次优化：排除偶数

原理：除了 2 之外，所有偶数都不是素数。先单独判断 2，再只检查奇数。

public static boolean isPrimeSkipEven(int n) {
    if (n <= 1) return false;
    if (n == 2) return true;
    if (n % 2 == 0) return false;
    // 只检查奇数，步长为 2
    for (int i = 3; i <= Math.sqrt(n); i += 2) {
        if (n % i == 0) return false;
    }
    return true;
}

• 时间复杂度：O(√n/2)
• 这是日常开发中最常用的单个素数判断方法

三、核心：埃拉托斯特尼筛法

当我们需要批量生成一定范围内的所有素数时，上面的逐个判断方法效率仍然不高。这就是本次作业的核心内容——埃拉托斯特尼筛法。

3.1 算法核心思想

用“筛沙子”的比喻来理解：

1. 准备一个“筛子”（布尔数组），初始时所有数字都被认为是素数（标记为 ✅）
2. 先把 0 和 1 这两个非素数扔掉（标记为 ❌）
3. 从第一个素数 2 开始，把筛子里所有 2 的倍数都筛掉
4. 找到下一个没被筛掉的数（下一个素数），重复筛掉它的所有倍数
5. 直到筛到 √max 为止，剩下的就全都是素数

3.2 分步演示（30 以内素数）

这部分用表格一步步还原每一轮的标记过程。

初始状态（第 0 轮）

创建大小为 31 的数组，全部初始化为 ✅，然后标记 0 和 1 为 ❌。

索引:  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
状态:  ❌ ❌ ✅ ✅ ✅ ✅ ✅ ✅ ✅ ✅ ✅ ✅ ✅ ✅ ✅ ✅ ✅ ✅ ✅ ✅ ✅ ✅ ✅ ✅ ✅ ✅ ✅ ✅ ✅ ✅ ✅

第 1 轮：处理 i=2（第一个素数）

• 发现 isPrime[2] = ✅，确认 2 是素数
• 标记所有 2 的倍数：4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30 → 全部设为 ❌

索引:  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
状态:  ❌ ❌ ✅ ✅ ❌ ✅ ❌ ✅ ❌ ✅ ❌ ✅ ❌ ✅ ❌ ✅ ❌ ✅ ❌ ✅ ❌ ✅ ❌ ✅ ❌ ✅ ❌ ✅ ❌ ✅ ❌

第 2 轮：处理 i=3（第二个素数）

• 发现 isPrime[3] = ✅，确认 3 是素数
• 从 3×3=9 开始标记倍数（6 已经被 2 标记过了）：9, 12, 15, 18, 21, 24, 27, 30 → 设为 ❌

索引:  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
状态:  ❌ ❌ ✅ ✅ ❌ ✅ ❌ ✅ ❌ ❌ ❌ ✅ ❌ ✅ ❌ ❌ ❌ ✅ ❌ ✅ ❌ ❌ ❌ ✅ ❌ ✅ ❌ ❌ ❌ ✅ ❌

第 3 轮：处理 i=4

• 发现 isPrime[4] = ❌，已经是合数，直接跳过

第 4 轮：处理 i=5（第三个素数）

• 发现 isPrime[5] = ✅，确认 5 是素数
• 从 5×5=25 开始标记倍数（10, 15, 20 已被标记）：25, 30 → 设为 ❌

索引:  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
状态:  ❌ ❌ ✅ ✅ ❌ ✅ ❌ ✅ ❌ ❌ ❌ ✅ ❌ ✅ ❌ ❌ ❌ ✅ ❌ ✅ ❌ ❌ ❌ ✅ ❌ ❌ ❌ ❌ ❌ ❌ ✅ ❌

算法结束！

• 因为 √30 ≈ 5.47，所以只需要处理到 i=5
• 最终所有 ✅ 的数就是 30 以内的素数：2, 3, 5, 7, 11, 13, 17, 19, 23, 29

四、关键疑问解答

1. 为什么只需要循环到 √max 就可以停止？

如果一个数 n 是合数，它一定可以分解为 a×b。其中 a 和 b 不可能都大于 √n，否则 a×b > √n×√n = n，矛盾。因此所有大于 √max 的合数，它的因数一定已经被小于 √max 的素数标记过了。

2. 为什么从 i×i 开始标记倍数，而不是从 2×i 开始？

对于素数 i，它的倍数 2×i, 3×i, …, (i-1)×i 已经被比 i 小的素数（2, 3, …, i-1）标记过了。从 i×i 开始可以避免重复标记，提高算法效率。

3. 筛法比逐个判断快多少？

算法	时间复杂度	生成 100 万以内素数耗时
暴力遍历法	O(n√n)	> 10000ms
平方根优化	O(n√n)	1245ms
埃拉托斯特尼筛法	O(n log log n)	12ms

测试环境：Intel i5-10400F，JDK 17

五、完整 Java 代码实现（可直接运行）

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

/**
 * 素数算法完整实现
 * Java 面向对象程序设计课程作业
 * 包含：单个素数判断、埃拉托斯特尼筛法、可视化分步演示
 */
public class PrimeNumbers {

    // 1. 基础暴力法
    public static boolean isPrimeBasic(int n) {
        if (n <= 1) return false;
        for (int i = 2; i < n; i++) {
            if (n % i == 0) return false;
        }
        return true;
    }

    // 2. 平方根优化
    public static boolean isPrimeSqrt(int n) {
        if (n <= 1) return false;
        for (int i = 2; i <= Math.sqrt(n); i++) {
            if (n % i == 0) return false;
        }
        return true;
    }

    // 3. 排除偶数优化
    public static boolean isPrimeSkipEven(int n) {
        if (n <= 1) return false;
        if (n == 2) return true;
        if (n % 2 == 0) return false;
        for (int i = 3; i <= Math.sqrt(n); i += 2) {
            if (n % i == 0) return false;
        }
        return true;
    }

    // 4. 核心：埃拉托斯特尼筛法
    public static List<Integer> sieveOfEratosthenes(int max) {
        if (max < 2) return new ArrayList<>();

        // 初始化筛子数组
        boolean[] isPrime = new boolean[max + 1];
        Arrays.fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;

        // 核心筛法过程
        for (int i = 2; i <= Math.sqrt(max); i++) {
            if (isPrime[i]) {
                // 从 i*i 开始标记倍数
                for (int j = i * i; j <= max; j += i) {
                    isPrime[j] = false;
                }
            }
        }

        // 收集所有素数
        List<Integer> primes = new ArrayList<>();
        for (int i = 2; i <= max; i++) {
            if (isPrime[i]) primes.add(i);
        }
        return primes;
    }

    // 5. 可视化演示
    public static void printSieveProcess(int max) {
        if (max < 2) {
            System.out.println("小于 2 的数没有素数");
            return;
        }

        boolean[] isPrime = new boolean[max + 1];
        Arrays.fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;

        System.out.println("=== 埃拉托斯特尼筛法 分步演示 ===");
        System.out.println("初始状态：");
        printArray(isPrime);

        for (int i = 2; i <= Math.sqrt(max); i++) {
            if (isPrime[i]) {
                System.out.println("\n第" + i + "轮：标记" + i + "的所有倍数");
                for (int j = i * i; j <= max; j += i) {
                    isPrime[j] = false;
                }
                printArray(isPrime);
            }
        }

        System.out.println("\n最终结果：");
        List<Integer> primes = new ArrayList<>();
        for (int i = 2; i <= max; i++) {
            if (isPrime[i]) primes.add(i);
        }
        System.out.println(max + "以内的素数：" + primes);
        System.out.println("素数个数：" + primes.size());
    }

    // 辅助方法：打印数组状态
    private static void printArray(boolean[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.printf("%2d:%s ", i, arr[i] ? "✅" : "❌");
            if ((i + 1) % 10 == 0) System.out.println();
        }
        System.out.println();
    }

    // 主方法：测试所有功能
    public static void main(String[] args) {
        // 1. 运行可视化演示
        printSieveProcess(30);

        // 2. 测试单个素数判断
        int testNum = 97;
        System.out.println("\n=== 单个素数判断测试 ===");
        System.out.println(testNum + " 是否为素数：");
        System.out.println("暴力法：" + isPrimeBasic(testNum));
        System.out.println("平方根优化：" + isPrimeSqrt(testNum));
        System.out.println("排除偶数优化：" + isPrimeSkipEven(testNum));

        // 3. 生成 100 以内的素数
        System.out.println("\n=== 100 以内的素数 ===");
        List<Integer> primes100 = sieveOfEratosthenes(100);
        System.out.println(primes100);

        // 4. 性能测试
        int testMax = 1000000; // 100 万
        long start = System.currentTimeMillis();
        List<Integer> primesMillion = sieveOfEratosthenes(testMax);
        long end = System.currentTimeMillis();
        System.out.println("\n=== 性能测试 ===");
        System.out.println(testMax + "以内的素数个数：" + primesMillion.size());
        System.out.println("埃拉托斯特尼筛法耗时：" + (end - start) + " ms");
    }
}

六、学习总结

通过这次作业，我理解了埃拉托斯特尼筛法的遍历过程。一开始只觉得这个算法的过程很抽象，直到自己一步步把每一轮的表格画出来，再结合代码逐行调试，才真正理解了这个算法的精髓。

我最大的收获有两点：

• 数学是算法的基础：无论是平方根优化还是筛法的终止条件，所有高效的优化都来自严谨的数学推导，而不是凭空想象。
• 算法优化的力量：从最基础的暴力法到埃氏筛法，运行时间从十几秒缩短到十几毫秒，这种数量级的提升让我深刻认识到算法的重要性。

作为一名大二的 Java 学习者，我之前更多关注的是语法和 API 的使用。通过这次作业，我意识到写出能运行的代码只是第一步，写出高效、优雅的代码才是我们应该追求的目标。在未来的学习中，我会更加注重算法思维的培养，不断提升自己的编程能力。