如何使用埃拉托色尼篩法在 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中文網其他相關文章！