改善我的Eratosthenes筛网的实现

Question

我正在创建Eratosthenes的筛网，以便更有效地求和1到大数n之间的素数。我想要做的是创建一个从2到n的列表，然后删除2的倍数，然后删除3的倍数，再删除列表中下一个数字的倍数，依此类推。我创建的代码在时间上性能很慢，几乎就像通过检查每个条目是否为质数来创建列表一样。我想我要进行的操作数是有序的：n的平方根（第一个while循环）乘以n的平方根（小于第二个while循环）。因此，我不确定remove方法或其他方法是否会降低它的速度。

我的代码是这个：

def sieve_of_Eratosthenes(n):
L= list(range(2,n+1))
# creates a list from 2 to n

i=2
while i*i <=n: # going to remove multiples of i, starting at i^2
    k=i        # if j <i then ij already checked
    while i*k <= max(L):
        try:
            L.remove(i*k)   # there is an error if the element is not in 
                            # the list so need to add these two lines
        except ValueError:  
            pass     # do nothing!
        k=k+1
    i=L[i-1]      # list index starts at 0, want i to be next element in the list
# print(L)
return L

Answer 1

假设

问题是有关如何改善软件的运行时间，因为它的运行速度很慢。

执行以下两个代码更改以加快代码的速度

1. 而不是保留素数列表，而是将数字检查为素数（真）或非Prime（False）
2. 仅检查奇数> 2是否为素数

代码

def sieve_of_Eratosthenes2(n):
    if n < 2:
        return []
    if n < 3:
        return [2]

    L = [True] * (n+1)    # all numbers set as primes initially

    # modifies prime flag in list for odd numbers
    for i in range(3, n, 2): # Check odd numbers for prime (no need to check even numbers)
        if L[i]: # A prime
            L[i*i::i] = [False]*len(L[i*i::i]) # from i^2 in increments of i

    # Report prime 2 + odd primes
    return [2] + [i for i in range(3, n, 2) if L[i]]  # Get odd numbers whose flag is 
                                                      # still True

新代码

%timeit sieve_of_Eratosthenes2(100000)
 16 ms ± 1.58 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

旧代码

 sieve_of_Eratosthenes2(100000)
 261.45 seconds  (using time module)