找出給定整數 N 以下的所有質數的最快方法是什麼？

列出N 以下所有素數的最快方法

此程式碼片段提供了有效產生素數列表的方法的Python 實現最多給定整數。

    def get_primes(n):
        numbers = set(range(2, n + 1))
        primes = []
        while numbers:
            p = numbers.pop()
            primes.append(p)
            numbers.difference_update(set(range(p * p, n + 1, p)))
        return primes

時間複雜度：

給定程式碼的時間複雜度為O(n log log n)，因為它使用埃拉托斯特尼篩法來計算質數。

實作說明:

• 程式碼初始化一組數字，其中包含從2 到n.
• 它透過將尚未標記的最小數字的所有倍數標記為合數，迭代地從數字中刪除非素數。在更新數字時，透過採用目前質數的步幅來跳過這些倍數。
• 當數字為空時，代碼停止，找到的素數列表以素數形式傳回。

潛在問題：

實現中存在一個潛在問題，它將起始數字標記為素數當它只應考慮從2 到n 的數字時。這可以透過從 2 而不是 0 開始循環來解決。

用法：

要使用此實現，您可以呼叫 get_primes 函數並傳遞所需的上限綁定為參數。例如，要找出1000 以內的所有質數，您可以使用：

primes = get_primes(1000)

輸出：

程式碼的輸出將是素數。例如，執行 n = 1000 的程式碼將產生以下輸出：

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, ..., 977]

以上是找出給定整數 N 以下的所有質數的最快方法是什麼？的詳細內容。更多資訊請關注PHP中文網其他相關文章！