如何使Eratosthenes的筛子更快？

我想解决项目欧拉中的10个问题。它包括找到所有素数低于200万的总和。我根据Eratosthenes的Sieve编写了以下代码。如何使Eratosthenes的筛子更快？

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太慢了。我非常感谢能够帮助改善这个计划。

来源

2015-06-17 Driss Alami

http://stackoverflow.com/a/23423821/2141635使用总和，你有答案 –

也有关：http://stackoverflow.com/q/2068372/1639625 –

相关：[加快位串/位操作在Python中？]（http://stackoverflow.com/q/2897297/4279） – jfs

总是尝试在几个范围内测量代码的empirical complexity。

您的代码很慢，因为您发现设置的差异，并且您总是在设置和列表之间进行转换并返回。你应该自始至终都使用一个设置，并与

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

更新它的地方找到的最小元素，你可以叫min(sete)上设定，无需转换列表。由于对最小元素的低效搜索，所得代码的总体复杂度将接近n^1.5，这不是太明亮，但也不太可怕。尤其是，它在ideone.com上的4.9秒内完成，找到200,000以下素数的总和，以及400,000的0.5秒（仅在首次使用赔率时进行了额外的优化）。

来源

2015-06-22 14:17:35

为了找到低于200000的素数总和，下面的代码（使用eratosthenes筛选）工作得更快，您的代码需要将近55secs，而下面的代码只需要0.8secs来执行！

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)

来源

2015-06-21 13:38:58

好代码，n^1.04的经验复杂度！ –

如何使Eratosthenes的筛子更快？

回答

相关问题