Python Eratosthenes 筛算法优化

我正在尝试实现埃拉托色尼筛法。输出似乎是正确的(减去需要添加的“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 

请您参考如下方法:

您的算法不是埃拉托色尼筛法。您执行试验除法(模数运算符)而不是像埃拉托色尼 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 上看到这个函数的运行情况。 ，它在不到一秒的时间内计算出一百万个素数。