生成低于给定整数 N 的所有素数的最快算法是什么？

列出 N 以下所有素数的最快方法：探索

问题：

确定列出所有素数的最快方法小于给定整数的素数N.

问题：

可以优化给定的算法以加快执行速度吗？

答案：

提供的算法可以显着提高速度。各种实现的比较表明，使用 Psyco 的 rwh_primes1 对于生成小于 1,000,000 的素数来说是最有效的。

其他发现：

• 没有 Psyco，rwh_primes2 就会出现作为最快的方法。
• 利用 NumPy 可以进一步增强性能，primesfrom2to 被证明是所有测试方法中最快的。

实现细节：

• ambi_sieve_plain：一个简单的基于筛子的
• rwh_primes、rwh_primes1 和 rwh_primes2：Robert William Hanks 算法的变体。
• sieve_wheel_30：针对基于 30 的计算进行优化的专用算法。
• sieveOfEratosthenes：带 bitset 的经典筛法优化。
• sieveOfAtkin：利用模算术的现代筛选。
• sundaram3：Sundaram 算法，针对较小数字集进行优化。
• ambi_sieve：基于 NumPy 的筛选方法优化。
• primesfrom3to 和primesfrom2to：基于 NumPy 的算法，用于高效生成素数。

计时：

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中文网其他相关文章！