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

您的算法不是埃拉托色尼筛法。您执行试验除法(模数运算符)而不是像埃拉托色尼 2000 多年前所做的那样交叉乘数。 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 的平方根处停止。 j 上奇怪的计算映射在被筛选的整数 3、5、7、9 ...... 和 b 中的索引 0、1、2、3 ...... 位数组。

您可以在 http://ideone.com/YTaMB 上看到这个函数的运行情况。 ，它在不到一秒的时间内计算出一百万个素数。