Улучшение реализации списка простых чисел

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))

(Редактировать: заменить список набором для эффективной замены)