我們如何優雅地生成質數？

優雅地產生素數

在程式設計中經常會遇到對素數產生函數的簡潔且可讀的實現的需求。一個這樣的函數，generatePrimes，旨在產生前 n 個質數的列表，從而提出了哪種方法最優雅的問題。

基本實作

一個常見的方法涉及一個簡單的方法迭代方法，從包含前幾個素數(2, 3) 的列表開始，並在驗證素數時逐步添加下一個質數。雖然功能強大，但由於其顯式循環結構和冗長檢查的可能性，此實作可能缺乏優雅性。

利用篩子演算法

更優雅的解決方案是採用篩子演算法，例如埃拉托色尼篩法。此方法初始化一個布林數組，表示在指定限制範圍內數字的潛在質數。從 2 開始，它迭代地將每個質數的倍數標記為非素數，從而有效地將它們從列表中消除。

<code class="java">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中文網其他相關文章！