產生低於給定整數 N 的所有質數的最快演算法是什麼？

列出 N以下所有質數的最快方法：探索

問題：

確定列出所有質數的最快方法小於給定整數的質數N.

問題：

可以最佳化給定的演算法以加快執行速度嗎？

答案：

提供的演算法可以顯著提高速度。各種實現的比較表明，使用 Psyco 的 rwh_primes1 對於產生小於 1,000,000 的素數來說是最有效的。

其他發現：

• 沒有 Psyco，rwh_primes2 就會出現作為最快的方法。
• 利用 NumPy 可以進一步增強效能，primesfrom2to 被證明是所有測試方法中最快的。

實作細節：

• ambi_sieve_plain：一個簡單的基於篩子的
• rwh_primess、wprih_primess、Pprim_primess、Robert演算法的變體。
• sieve_wheel_30：針對基於 30 的計算進行最佳化的專用演算法。
• sieveOfEratosthenes：帶 bitset 的經典篩法優化。
• sieveOfAtkin：利用模算術的現代篩選。
• sundaram3：Sundaram 演算法，針對較小數位集進行最佳化。
• ambi_sieve：基於 NumPy 的篩選方法最佳化。
• primesfrom3to 和primesfrom2to：基於 NumPy 的演算法，用於高效產生質數。

計時：

tr> 147.0

方法

使用Psyco 的時間（毫秒）

不使用Psyco的時間（毫秒）心理

rwh_primes1

43.0

93.7

sieveOfAtkin

46.4

314.0

rwh_primes

57 .4

94.6

sieve_wheel_30

63.0

97.4

rwh_primes2

67.8

68.1

埃拉托斯特尼篩

178.0

ambi_sieve_plain

152.0

286.0

sundaram3

194.0

416.0

primesfrom2to

Method	Time (ms) with Psyco	Time (ms) without Psyco
rwh_primes1	43.0	93.7
sieveOfAtkin	46.4	314.0
rwh_primes	57.4	94.6
sieve_wheel_30	63.0	97.4
rwh_primes2	67.8	68.1
sieveOfEratosthenes	147.0	178.0
ambi_sieve_plain	152.0	286.0
sundaram3	194.0	416.0
primesfrom2to	15.9	N/A
primesfrom3to	18.4	N/A
ambi_sieve	29.3	N/A

15.9

不適用

primesfrom3to

18.4

不適用

ambi_sieve

29.3

不適用

以上是產生低於給定整數 N 的所有質數的最快演算法是什麼？的詳細內容。更多資訊請關注PHP中文網其他相關文章！