改进素数列表的实现

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 prime


PrimeSet = set()

for x in range(2, 11111):
    print(x, PrimeSieve(x))

（编辑：将列表替换为有效替换的集合）