我們如何有效率地找到給定範圍內的所有質數？

找出給定範圍內的素數：最佳化方法

本文解決了有效辨識指定範圍內所有質數的挑戰。 質數，根據定義，是大於 1 的自然數，除了 1 和它本身之外沒有正因數。

有缺陷的方法及其修正

解決此問題的初步嘗試在邏輯上存在嚴重缺陷。程式碼從 0 開始迭代，錯誤地將 0 和 1 作為潛在素數，並使用了錯誤的素性測試。條件 if (i != j && i % j == 0) 辨識合數，而不是質數。 正確的方法是檢查一個數字是否不能被除 1 和它本身以外的任何數字整除。

使用試分篩的最佳化解決方案

一種更有效的方法是利用試分篩。 這種方法利用了幾個關鍵的最佳化：

1. 平方根極限：我們只需要測試目標數的平方根的整除性。如果一個數有一個大於其平方根的除數，那麼它也必須有一個小於其平方根的除數。

2. 倍數刪除：一旦辨識出素數，其倍數就會從候選清單中刪除，大大減少後續檢查的次數。

3. 迭代估計：程式碼使用近似公式（π(x)

優化後的程式碼（為了簡潔而使用LINQ）有效地實現了這個策略：

Enumerable.Range(0, Math.Floor(2.52*Math.Sqrt(num)/Math.Log(num))).Aggregate(
    Enumerable.Range(2, num-1).ToList(), 
    (result, index) => { 
        var bp = result[index]; var sqr = bp * bp;
        result.RemoveAll(i => i >= sqr && i % bp == 0); 
        return result; 
    }
);

與簡單的方法相比，這種改進的演算法提供了顯著的效能改進，特別是在處理廣泛的範圍時。 使用 Enumerable.Range、ToList、RemoveAll 和 Aggregate 可以實現緊湊且高效的實現。

以上是我們如何有效率地找到給定範圍內的所有質數？的詳細內容。更多資訊請關注PHP中文網其他相關文章！