如何有效率地映射一定範圍內的質數？

高效映射範圍內的素數

確定指定範圍內的素數是一項常見的程式設計任務。為了優化此任務的記憶體消耗，我們尋求一種演算法，該演算法可以創建最緊湊的資料結構來表示給定範圍(1, N] 的素數。

素數範圍映射的建議演算法

一般素數測試最有效的演算法是AKS 演算法，但是，出於有限範圍內的實際目的，經典O(sqrt(N)) 演算法的以下變體可以提供有效的解決方案：

def isprime(n):
    if n == 2 or n == 3:
        return True
    if n % 2 == 0 or n % 3 == 0:
        return False
    # Check prime divisors of the form 6k - 1 and 6k + 1
    i = 5
    w = 2
    while i * i <= n:
        if n % i == 0:
            return False
        i += w
        w = 6 - w
    return True

演算法分析

演算法依賴於這樣一個事實：所有大於3 的素數都是6k - 1 或6k 通過 1 的形式。以這種模式迭代潛在的素數，該演算法可以有效地識別非素數。有限時，基於費馬小定理實現偽素數測試是有效的，但是這種方法有範圍限制。此演算法是消除所有作為潛在素數的偶數。

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