如何使埃拉托色尼筛法更快？

Question

我正在尝试解决 Project Euler 中的第 10 个问题。它包括找到 200 万以下所有素数的总和。我根据埃拉托色尼筛法编写了以下代码。

import time
t0 = time.time()
n=200000
liste=list(range(2,n))
k=2
s=2
while k <=n:
    liste=list(set(liste)-set(range(k,n,k)))
    if liste!=[]:
        k=min(liste)
        s+=k
    else:
        break
print(s)
t1 = time.time()
total = t1-t0
print(total)

我针对n=200000 测试了上面的代码，但是对于n=2000000 来说太慢了。如果能得到任何改进此程序的帮助，我将不胜感激。

Answer 1

为了找到小于 200000 的素数之和，下面的代码（使用埃拉托色尼筛法）工作得更快，您的代码需要将近 55 秒，而下面的代码只需 0.8 秒即可执行！

import time
t0 = time.time()
n = 200000
sieve = [True] * (n + 1)
for i in range(2, n + 1) :
  if sieve[i] :
     for mult in range(i + i, n + 1, i) :
        sieve[mult] = False
s=0     
for i in range(2,n + 1):
    if sieve[i] :
        s+=i    
print(s)
t1 = time.time()
total = t1-t0
print(total)

Answer 2

始终尝试在多个范围内测量 empirical complexity 代码。

你的代码很慢，因为你找到集合差异的方式，而且你总是在集合和列表之间来回转换。您应该始终使用一套，并使用

对其进行更新

    sete.difference_update(range(p*p,n,p*2))

要查找最小元素，只需调用集合上的 min(sete) 即可，无需列表转换。

由于对 min 元素的低效搜索，最终代码的整体复杂度将接近 n^1.5，这不算太亮，但也不算太糟糕。特别是，它在 ideone.com 上用不到 4.9 秒完成，找到 2000000 以下素数的总和，400000 以下的素数总和为 0.5 秒（首先对仅使用赔率进行了额外优化）。

如何使埃拉托色尼筛法更快？

How to make the Sieve of Eratosthenes faster?

python

primes

sieve-of-eratosthenes

number-theory

python-3.x