Python-Eratosthenes筛算法优化

Question

我正在尝试实施埃拉托斯泰尼的筛子。输出似乎是正确的（减去需要添加的“2”），但如果函数的输入大于100k，则似乎需要花费大量的时间。有什么方法可以优化这个功能？在

def sieveErato(n):
     numberList = range(3,n,2)

     for item in range(int(math.sqrt(len(numberList)))):
            divisor = numberList[item]
            for thing in numberList:
                    if(thing % divisor == 0) and thing != divisor:
                            numberList.remove(thing)
    return numberList

Answer 1

你的算法不是埃拉托斯提尼的筛子。您可以执行试除法（模运算符），而不是像两千多年前埃拉托什涅斯（Eratosthenes）那样去掉倍数。Here是对真筛选算法的一种解释，下面是我的简单、直接的实现，它返回一个不超过n的素数列表：

def sieve(n):
    m = (n-1) // 2
    b = [True]*m
    i,p,ps = 0,3,[2]
    while p*p < n:
        if b[i]:
            ps.append(p)
            j = 2*i*i + 6*i + 3
            while j < m:
                b[j] = False
                j = j + 2*i + 3
        i+=1; p+=2
    while i < m:
        if b[i]:
            ps.append(p)
        i+=1; p+=2
    return ps

我们只筛选奇数，停在n的平方根。对3、5、7、9等整数之间的j映射的奇数计算。。。索引0，1，2，3。。。在b位数组中。在

您可以在http://ideone.com/YTaMB处看到这个函数的作用，它在不到一秒钟的时间内将素数计算到一百万。在

Answer 2

警告：在迭代时从迭代器中删除元素可能会非常密集。。。在

你可以

    if(thing % divisor == 0) and thing != divisor:

测试打火机，方法是在循环中拆分它，当到达“除数”的索引时，该循环中断，然后测试：

^{2}$

Answer 3

你可以试试埃拉托斯泰尼的方法。取一个数组，其中包含所有需要检查升序的数字，转到数字2并标记它。现在每秒钟抓取一个数字直到数组的末尾。然后转到3并标记。在那之后，每三个数字都被划伤一次。然后转到4-它已经被划伤了，所以跳过它。对尚未划伤的n+1重复此操作。在

最后，标记的数字是素数。该算法速度较快，但有时需要大量内存。您可以通过删除所有偶数（因为它们不是素数）并手动在列表中添加2来优化它。这会稍微扭曲逻辑，但会占用一半的内存。在

下面是我所说的一个例子：http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes