如何優化埃拉托斯特尼篩演算法以加快素數生成速度？

埃拉托色尼篩法

埃拉托色尼篩法是一種古老的演算法，但今天仍然被用作一種簡單而有效的方法來找出低於給定數字的所有質數。這個演算法的工作原理是迭代地標記每個質數的倍數，從 2 開始。

這是埃拉托斯特尼篩法的 Python 實作：

def sieve_of_eratosthenes(n):
    """Return a list of all prime numbers below n."""

    # Create a list of all numbers from 2 to n.
    numbers = list(range(2, n + 1))

    # Iterate over the numbers in the list.
    for i in range(2, int(n ** 0.5) + 1):

        # If the number is prime, mark off all its multiples.
        if numbers[i] != -1:
            for j in range(i * i, n + 1, i):
                numbers[j] = -1

    # Return the list of prime numbers.
    return [i for i in numbers if i != -1]

這個演算法實作起來相對簡單，而且效率很高。例如，它可以在現代電腦上大約 0.1 秒內找到 100 萬以下的所有質數。

時間複雜度

埃拉托斯特尼篩法的時間複雜度為 O(n log log n) 。這意味著演算法需要 O(n) 時間來建立從 2 到 n 的所有數字的列表，並且需要 O(log log n) 時間來標記每個質數的所有倍數。

可以做得更快嗎？

有幾種方法可以讓埃拉托斯特尼篩變得均勻更快：

• 使用更有效率的資料結構。 從2到n的所有數字的列表可以儲存在更有效率的資料結構中，例如位元向量。這可以減少演算法的空間需求並提高其效能。
• 使用更有效率的標記演算法。 可以使標記每個質數的所有倍數的演算法更有效率地通過使用篩輪。這可以將演算法的時間複雜度降低到 O(n)。
• 平行化演算法。 可以並行化演算法以利用現代電腦上的多個內核。這可以進一步提高演算法的效能。

這是埃拉托斯特尼篩法的更快版本的Python 實現：

import numpy as np

def sieve_of_eratosthenes_fast(n):
    """Return a list of all prime numbers below n."""

    # Create a bit vector to store the prime numbers.
    primes = np.ones(n // 2 + 1, dtype=np.bool)

    # Mark off all the multiples of 2.
    primes[3::2] = False

    # Iterate over the odd numbers from 3 to n.
    for i in range(3, int(n ** 0.5) + 1, 2):

        # If the number is prime, mark off all its multiples.
        if primes[i // 2]:
            primes[i * i // 2::i] = False

    # Return the list of prime numbers.
    return [2] + [2 * i + 1 for i in range(1, n // 2 + 1) if primes[i]]

該演算法比原始版本更快埃拉托斯特尼篩法，它可以在現代計算機上大約0.01 秒內找到100 萬以下的所有素數電腦。

以上是如何優化埃拉托斯特尼篩演算法以加快素數生成速度？的詳細內容。更多資訊請關注PHP中文網其他相關文章！