Java 中的 Eratosthenes 筛法算法

埃拉托斯特尼筛法是一种古老而高效的算法，用于找出给定范围内的所有素数。该算法以古希腊数学家埃拉托斯特尼·希腊命名，经受住了时间的考验，至今仍是数论和计算机科学中的基本概念。在本节中，我们将深入探讨埃拉托斯特尼筛法的机制，并用 Java 实现它，以了解它是如何高效地识别素数的。

理解埃拉托斯特尼筛法算法

埃拉托斯特尼筛法的工作原理是通过迭代地划掉每个素数（从 2 开始）的倍数，从而揭示素数并消除非素数。该算法的主要步骤如下：

创建一个布尔数组来表示从 2 到给定上限的数字范围。

将数组中的所有元素初始化为 true，因为最初所有数字都被认为是素数。

从第一个素数（2）开始，将其所有倍数标记为非素数，方法是将它们在数组中对应的元素设置为 false。

找到数组中下一个仍标记为素数的数字，并重复步骤 3。

持续此过程，直到达到给定上限的平方根，因为此后不需要考虑任何非素数。

Java 实现埃拉托斯特尼筛法

下面是埃拉托斯特尼筛法算法的 Java 实现：

文件名：SieveOfEratosthenes.java

输出

Prime numbers up to 50: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

解释

findPrimes() 方法接受一个整数上限作为输入，并返回给定上限内的所有素数列表。

isPrime() 布尔数组被初始化，用于存储从 2 到上限的每个数字的素性状态。

外层循环从第一个素数 2 开始，一直迭代到上限的平方根。对于每个素数 p，内层循环通过将对应的 isPrime() 数组元素设置为 false 来划掉它的所有倍数。

完成标记过程后，该算法将所有素数（在 isPrime() 数组中标记为 true）收集到 primes 列表中。

最后，main 方法演示了如何使用 findPrimes() 方法，通过找出 50 以内的素数并打印结果。

该程序使用埃拉托斯特尼筛法成功找出并打印了 50 以内的所有素数。素数列表为 [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]。这些数字除了 1 和它们本身之外没有其他除数。

结论

埃拉托斯特尼筛法是找出给定范围内素数的一种强大而高效的方法。其时间复杂度为 O(n*log(log(n)))，优于许多其他素数查找算法，使其成为各种数学和计算应用中的重要工具。本文提供的 Java 实现展示了如何使用现代编程语言来实现这种古老的算法来高效地解决实际问题。无论是为了数论还是性能优化，理解埃拉托斯特尼筛法对任何程序员来说都是一项宝贵的财富。