有关欧拉 10 的建议，试图理解埃拉托斯特尼筛法

Question

过去几天我一直在研究这个问题 10，并且我一直在努力改进运行时间，而不是让它运行超过半小时到一个小时。起初，它检查每个值是否为素数并删除，然后我发现了埃拉托斯特尼筛法并尝试实现它。我不确定我是否在这里取得了进步。

goal = 2000000
allBelow = [int(x) for x in range(0,goal)]

def sieveOut(lst:list,value:int):
    index = lst.index(value)
    while index < len(lst):
        v=lst[index]
        if v != value and v%value == 0:
            print("REMOVING: " + str(v))
            lst.remove(v)
        index+=value
    return lst

index = 0
allBelowLength = len(allBelow)
while index < allBelowLength:
    value = allBelow[index]
    if value <= 1:
        print("Removing " + str(value))
        allBelow.remove(value)
    else:
        print("Sieving out " + str(value))
        allBelow = sieveOut(allBelow,value)
        index += 1
    allBelowLength = len(allBelow)

print(str(allBelow) + " :: " + str(sum(allBelow)))

Answer 1

看起来您在埃拉托斯特尼筛法方面进展顺利，但您的实施还可以改进。

lst.remove(v)

可能是关键点，因为所有元素都必须移动。

您的实施可以这样改进：

def sieve_of_eratosthenes(max_number):
    is_a_prime_number = [True for i in range(max_number+1)]  # at first, no values are sieved out
    p = 2  # p is the number being checked. starts at value 2 and counts up the squareroot of max_number
    while (p ** 2 <= max_number):
        if (is_a_prime_number[p] == True):  # this gets false for numbers where we actually know that they are no prime numbers (e.g., 6: we do not need to check multiples of 6, because the have been sieved out by 2)
            for i in range(p ** 2, max_number+1, p):
                is_a_prime_number[i] = False
        p += 1
    prime_numbers = [p for p in range(2, max_number) if is_a_prime_number[p]]
    return prime_numbers