为什么我的埃拉托色尼筛运行得这么慢？

Question

我正在为厄拉多塞的筛子用Python写一个素数程序。虽然看起来很管用，但是很慢。我该如何加快速度呢？

primes = []
upperLimit = 1000

for x in range(2,upperLimit):
  primes.append(x)
for y in range(0,int(len(primes)**0.5)):
  remove = []
  for j in range(primes[y]**2,upperLimit,primes[y]):
    remove.append(j)
  for i in remove:
    if i in primes:
      primes.remove(i)

print(primes)

更新：由于答案的帮助，我用布尔值而不是数字重写了代码。低于100000的列表现在运行时间不到6秒。

i = 2
limit = 100000
primes = [True] * limit
primes[0] = False
while i < limit**0.5:
    if primes[i-1]:
        for x in range(i * 2, limit + 1,i):
            primes[x-1] = False
    i += 1
count = 1
total = []
for i in primes:
    if i:
        total.append(count)
    count += 1
print(total)

Answer 1

它很慢，因为有许多操作你做得比需要的多得多。合数N的寿命看起来像这样:

< li >向素数追加N < li >对于每个小数字I(

• 如果我还在素数中，请将其删除。

每个数字都有很多“接触”。这也是许多需要考虑的小数字。

相反，请尝试以下操作：

• 列出布尔值（全部为 True），每个潜在素数对应一个布尔值。
• 而最低值我标记为 True

在这一点上，你的质数正是那些仍然标记为真的值

Answer 2

我认为，代码中的主要低效是您维护的素数的列表。尽管调用primes可能并不明显。删除是一个非常昂贵的操作。它需要遍历列表以尝试找到要删除的值，然后需要通过将所有元素移动到您要查找的元素之后来修改list。

例如。

l = [0, 1, 2, 3, 4]
l.remove(5)  # This has to look at all the elements in l, since 6 isn't there
l.remove(0)  # This finds 1 quickly but then has to move every element to the left

对于埃拉托斯特尼筛子，一种更传统的方法是使用一个数组（Python中的列表），其中包含您正在考虑的所有数字，其中每个元素都是一个布尔值，指示该数字是否可以是素数。

模仿上面的例子：

l = [True, True, True, True, True]
l[0] = False  # Just goes straight to that element and changes its value

下面是如何编写该代码的示例：

primes = [True] * 100000

# We already know 2 is the first prime
primes[0] = False
primes[1] = False

# Fine to stop at sqrt(len(primes)) here as you're already doing    
for i in range(2, len(primes)):
    if primes[i]:
        for j in range(i**2, len(primes), i):
            primes[j] = False

print([n for n, is_prime in enumerate(primes) if is_prime])

您会发现这要快得多，因为索引到列表并以这种方式更改值非常有效。