生成前 N 个素数的最优雅的方法是什么？

优雅生成素数的方法

目标是编写一个函数 generatePrimes(n)，返回前 n 个素数。有多种方法可以实现此功能，各有优劣。本文探讨最优雅的方法。

最初的方法通常使用嵌套循环来检查素数。虽然这种方法有效，但由于其重复性和嵌套结构，缺乏优雅性。更巧妙的方法是使用埃拉托斯特尼筛法，其时间复杂度为 O(n log log n)。

埃拉托斯特尼筛法的工作原理是创建一个大小为 n 的布尔数组，所有元素最初都设置为 true。数组索引表示从 0 到 n-1 的数字。算法首先将索引 0 和 1 处的元素设置为 false，因为它们不是素数。然后，对于每个索引 i，它将数组中 i 的所有倍数设置为 false。这个过程对所有索引重复，直到 n 的平方根。数组中剩余的 true 元素表示素数。

以下是埃拉托斯特尼筛法的一种优雅的 Java 实现：

public static List<Integer> generatePrimes(int n) {
    if (n <= 0) {
        return new ArrayList<>();
    }
    boolean[] isPrime = new boolean[n + 1];
    Arrays.fill(isPrime, true);
    isPrime[0] = isPrime[1] = false;
    for (int p = 2; p * p <= n; p++) {
        if (isPrime[p]) {
            for (int i = p * p; i <= n; i += p) {
                isPrime[i] = false;
            }
        }
    }
    List<Integer> primes = new ArrayList<>();
    for (int i = 2; i <= n; i++) {
        if (isPrime[i]) {
            primes.add(i);
        }
    }
    return primes;
}

这段代码使用埃拉托斯特尼筛法高效且优雅地生成了前 n 个素数。时间复杂度为 O(n log log n)，代码简洁明了，是生成素数的理想选择。

以上是生成前 N 个素数的最优雅的方法是什么？的详细内容。更多信息请关注PHP中文网其他相关文章！