埃拉托斯特尼筛法生成素数的效率如何？

最优雅的素数生成：筛法

当面临生成素数的挑战时，力求代码优雅是一种崇高的追求。虽然存在许多查找素数的方法，但埃拉托斯特尼筛法因其简单性和高效性而脱颖而出。

埃拉托斯特尼筛法通过创建长度为 n 的布尔数组来运行，该数组表示从 1 到 n 的数字。数组的所有元素最初都设置为 true，表示每个数字都是潜在的素数。然后，该算法从第一个未标记的数字（即 2）开始迭代数组。它通过将数组中的值设置为 false，将 2 的所有倍数标记为非素数。然后它移动到下一个未标记的数字 3，并重复该过程，将 3 的所有倍数标记为非素数。这一直持续到最后一个未标记的数字 √(n)。

通过使用这种方法，埃拉托斯特尼筛法显着减少了查找素数所需的检查次数，提供了高效的解决方案。考虑以下 Sieve 的 Java 实现：

<code class="java">public static BitSet computePrimes(int limit) {
    BitSet primes = new BitSet();
    primes.set(0, false);
    primes.set(1, false);
    primes.set(2, limit, true);
    for (int i = 0; i * i < limit; i++) {
        if (primes.get(i)) {
            for (int j = i * i; j < limit; j += i) {
                primes.clear(j);
            }
        }
    }
    return primes;
}</code>

此代码创建一个 BitSet 来表示从 1 到 n 的数字，并将所有元素初始设置为 true。然后它迭代数组，将每个素数（从 2 开始）的所有倍数标记为非素数。结果是一个 BitSet，其中唯一设置为 true 的元素代表素数。

以上是埃拉托斯特尼筛法生成素数的效率如何？的详细内容。更多信息请关注PHP中文网其他相关文章！