这段非常简短的 #Python 代码试图模拟“埃拉托色尼筛法”来处理前 N 个自然数,并具有以下限制:(0)脚本长度要短;(1)最小化“if语句”和“for/while循环”;(2)在 CPU 时间方面高效。
import numpy as np
N = 10**5
a = np.array(range(3,N,2))
for j in range(0, int(round(np.sqrt(N),0))):
a[(a!=a[j]) & (a%a[j] == 0)] = 0
a = a[a!=0]
a = [2]+list(a)
在Intel Core I5上,它返回前:
- N = 100,000的质数,用时0.03秒;
- N = 1,000,000的质数,用时0.63秒;
- N = 10,000,000的质数,用时22.2秒。
有人想分享更有效率的代码以满足上述限制吗?
numpy
不是一个很好的性能选择。正如kazemakase所指出的,这并不是真正的筛法,因为你要迭代地检查模数。此外,如果您真的想要提高性能,(a!=a[j]) & (a%a[j] == 0)
是一种非常浪费的操作。 - juanpa.arrivillaga