如何使用埃拉托色尼筛法在 Java 中优雅地生成素数？

Java中的埃拉托斯特尼筛法：优雅地生成素数

引言

素数生成是计算机科学中的一个基本问题，有多种算法可供选择。其中，埃拉托斯特尼筛法以其简洁性和效率而著称。本文提供了一个优雅的Java实现，使用埃拉托斯特尼筛法生成前n个素数。

埃拉托斯特尼筛法

埃拉托斯特尼筛法是一种概率算法，通过迭代消除素数的倍数来识别素数。它首先初始化一个布尔标志数组，每个标志代表一个不超过指定限制的数字。然后，算法从第一个素数2开始迭代遍历数组，并将它的所有倍数标记为非素数。此过程持续进行，直到限制内的所有数字都被消除，只留下素数。

优雅的实现

埃拉托斯特尼筛法的优雅Java实现如下所示：

public static BitSet computePrimes(int limit) {
    final BitSet primes = new BitSet();
    primes.set(0, false);
    primes.set(1, false);
    primes.set(2, limit, true);
    for (int i = 2; i * i <= limit; i++) {
        if (primes.get(i)) {
            for (int j = i * i; j <= limit; j += i) {
                primes.set(j, false);
            }
        }
    }
    return primes;
}

说明

此实现创建了一个BitSet，每个位代表一个不超过指定限制的数字。最初，0和1被标记为非素数，其他所有数字都被标记为素数。

外循环从第一个素数2开始迭代遍历数组。如果当前位置的位被设置（表示它是素数），则内循环将该素数的所有倍数标记为非素数。此过程持续进行，直到限制内的所有数字都被消除。

最后，返回包含素数的BitSet。

结论

这个Java实现的埃拉托斯特尼筛法展示了该算法的优雅和简洁性。它高效地生成素数，并具有清晰、合乎逻辑的结构。代码针对性能和易理解性进行了优化，对于需要素数生成器的程序员来说，它是一个宝贵的工具。

以上是如何使用埃拉托色尼筛法在 Java 中优雅地生成素数？的详细内容。更多信息请关注PHP中文网其他相关文章！