我正在用Python编写一个质数程序，用于eratothenes的筛选虽然看起来很管用，但速度很慢。我怎样才能加快速度？
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)
最佳答案
我相信你的代码的主要低效是你所维护的素数的list尽管这可能不明显，但调用primes.remove是一个非常昂贵的操作它需要遍历list以尝试找到要删除的值，然后需要通过在您要查找的元素之后移动所有元素来修改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
一种更传统的方法是使用一个数组（
list在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])
你会发现这是非常快的，因为索引到一个
list并且改变一个值是相当有效的。