改进这个质数列表实现

Question

以下代码列出了所有质数。这是埃拉托色尼筛法的新实现吗？当代码达到更高的数字时，如何改进代码以使其运行得更快？def PrimeSieve(curNum):    prime = True    del updateList[:]    for cp in PrimeList:        daPrime, daSkip = cp        if curNum == daSkip:            prime = False            upcp = (daPrime, daSkip + daPrime)            updateList.append(upcp)        else:            updateList.append(cp)    if prime:        updateList.append((curNum,2*curNum))    return primePrimeList = []updateList = []for x in range(2, 1111):    print(x, PrimeSieve(x))    del PrimeList[:]    for i in updateList:        PrimeList.append(i)

Answer 1

可能有很多方法可以改进这一点，但最让我印象深刻的是 - 为什么你有 updateList 和 PrimeList，你在每次迭代时不断删除和复制它们。随着列表变长，这需要更多时间。摆脱其中一个将是我的第一个改变。

def PrimeSieve(curNum):

    prime = True

    addSet = set()

    delSet = set()

    for cp in PrimeSet:

        daPrime, daSkip = cp

        if curNum == daSkip:

            prime = False

            addSet.add((daPrime, daSkip + daPrime))

            delSet.add(cp)

    if prime:

        addSet.add((curNum, 2 * curNum))

    PrimeSet.difference_update(delSet)

    PrimeSet.update(addSet)

    return prime

PrimeSet = set()

for x in range(2, 11111):

    print(x, PrimeSieve(x))