埃拉霍斯特内斯筛分优化

Question

几周前，我用python编写了erathostenes算法，如下所示：

def erathostenes(n):

    A = range(2,n+1)
    B = []
    i = 0

    while A[i] < math.sqrt(n):
        B.append(A[i])
        j = i
        aux = A[i]
        while j < len(A):
            if A[j]%aux == 0:
                A[j] = 0
            j += aux
        i += 1
        while A[i] == 0:
            i +=  1
    for i in range(len(A)):
        if A[i] != 0:
            B.append(A[i])
        i += 1
    return B

考虑了一下（我在编程方面不在行），我只是对我的算法做了一些修改，现在看起来像：

^{pr2}$

如果我用n=10.000.000执行算法，第一个代码的执行时间大约是7秒，第二个代码大约是4秒。在

对我的算法还有什么优化吗？谢谢！在

Answer 1

尝试做一个非循环版本只是为了好玩。结果是这样的：

def erathostenes(n):

    def helper_function(num_lst, acc):

        if not num_lst:
            return acc
        if len(num_lst) == 1:
            acc.append(num_lst[0])
            return acc
        num = num_lst.pop(0)
        multiples = ([x for x in range(num + 1, num_lst[-1] + 1) 
                         if x % num == 0])

        remains = ([x for x in num_lst if x not in multiples])
        acc.append(num)
        return helper_function(remains, acc )
    return helper_function(range(2, n + 1), [])

当我运行计时时，得到了826us的post-erathostenes（1000），和26ms的我的版本（！！）。令我惊讶的是它如此之慢。在

函数式编程它更有趣，但在Python中，外观并不适合这个问题（我的猜测是，如果使用功能性更强的语言，它会更快）。在

所以我试了一个命令式的版本。看起来像这样：

^{pr2}$

把整数列表的标志改成False。从直觉上看，迭代速度更快，对吧？在

我的结果是831ms的erathostenes_命令（100000），而你的版本是1.45。在

遗憾的是，命令式写得更快。代码和所有的fors，whiles，i's和j's看起来太乱了

Answer 2

您的代码中有错误。改变

while A[i] < raiz:

打开

^{pr2}$

当N为平方时，可以发现误差。在

对于优化，使用xrange代替range范围。在

Answer 3

i += 1 

最后一个循环很有趣。在

考虑更换

^{pr2}$

与

for i in xrange(LenA) 

你可以避免生成一个你不需要的庞大列表。在

编辑：

还要考虑一下：

    for j in xrange(i,lenA,aux):

而不是：

    while j < lenA:

然后修复错误

while A[i] <= raiz: 

就像fryday建议的那样。在