如何高效產生質數？

優雅且有效率地產生素數

在程式設計領域，尋找一種優雅且高效的方式來產生素數是一個經典挑戰。讓我們探索一種在簡潔性和性能之間取得平衡的方法。

考慮使用質數定理，定理將小於或等於 n 的質數數量估計為 pi(n) ≈ n / log(n) 。此估計值提供了可用於識別素數的篩子大小的上限。

篩法，也稱為埃拉托斯特尼篩法，迭代一系列數字並消除所有非 -通過將它們標記為複合素數。對於此任務，我們可以利用 BitSet 來表示質數集合，每個位元對應於範圍內的一個數字。

以下是這種優雅且高效的素數生成方法的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>

這種方法在典型筆記型電腦上大約一秒內有效地生成前一百萬個素數。其精度和速度的結合使其成為在各種計算場景中生成素數的寶貴工具。

以上是如何高效產生質數？的詳細內容。更多資訊請關注PHP中文網其他相關文章！