確定指定範圍內的素數是一項常見的程式設計任務。為了優化此任務的記憶體消耗，我們尋求一種演算法，該演算法可以創建最緊湊的資料結構來表示給定範圍(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中文網其他相關文章！
