Java实现输出100000以内的质数及算法优化：我的学习历程

作为一名程序员，最近我在简书平台上发现了一个很有趣的话题——如何用Java实现输出100000以内的质数，并对算法结构进行优化。这不仅是一次技术上的挑战，更是一场自我提升的旅程。

在开始之前，我们先来简单了解一下质数的概念。质数是指大于1且只能被1和它本身整除的自然数。例如2、3、5、7等都是质数，而4、6、8则不是。

刚开始接触这个问题时，我尝试了最简单的暴力破解方法。这种方法的逻辑很简单：对于每一个数字n，从2到n-1逐一检查是否能被n整除。如果都不能整除，则说明n是一个质数。

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

虽然这种方法容易理解，但它的效率非常低。当需要处理较大的范围时，比如100000以内的所有质数，计算时间会变得难以接受。

为了提高效率，我引入了平方根优化的思想。根据数学原理，一个数如果不能被小于或等于其平方根的任何数整除，那么它就是质数。

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

通过这个优化，程序的运行速度得到了显著提升。然而，当我将范围扩大到更大的数据集时，仍然感到力不从心。

经过一番研究，我发现了一种更为高效的算法——埃拉托色尼筛法（Sieve of Eratosthenes）。这种算法的基本思想是：从2开始，将每个质数的倍数标记为非质数，直到遍历完所有数为止。

public static List<Integer> sieveOfEratosthenes(int max) {
    boolean[] isPrime = new boolean[max + 1];
    Arrays.fill(isPrime, true);
    isPrime[0] = isPrime[1] = false;
    for (int i = 2; i * i <= max; i++) {
        if (isPrime[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;
}

使用埃拉托色尼筛法后，程序的性能大幅提升，能够在极短的时间内完成100000以内所有质数的计算。

这次学习经历让我深刻体会到算法优化的重要性。从最初的暴力破解法，到后来的平方根优化，再到最终采用埃拉托色尼筛法，每一步都让我对编程有了更深的理解。未来，我将继续探索更多高效算法，不断提升自己的技术水平。