改进这个质数列表实现

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 prime

PrimeList = []

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 primePrimeSet = set()for x in range(2, 11111):    print(x, PrimeSieve(x))