Python篩素數

Question

我想在Python 2.7上使用篩所有素數的總和。然而，當我運行這個程序時，我每次只能得到0。 我不知道爲什麼會發生這種情況。

import math,time 

start=time.clock() 

def primesieve(limit): 
    final=0 
    a=[True]*limit 
    a[0]=a[1]=False 
    for i,isprime in enumerate(a): 
    if isprime: 
     for n in xrange(i,limit,i): 
     a[n]=False 
    for i in xrange(limit): 
    if a[i]: 
     final=final+i 
    return final 

print primesieve(2000000) 

elapsed=time.clock()-start 

print elapsed 

Answer 1

for n in xrange(i,limit,i): 
    a[n]=False 

它應該是：

for n in xrange(2*i,limit,i): 
    a[n]=False 

或者，更有效地：

for n in xrange(i*i,limit, 2*i): #assuming you already cleared even numbers 
    a[n]=False 

因爲否則你最終會設立i作爲非黃金，當它實際上是一個主要。 （篩應該標誌着i非質數的倍數，除了i本身！）

---

注意你遍歷所有的數字，高達limit，但你可以達到sqrt(limit)後安全停止：達到limit平方根之後

import itertools as it 

def primesieve(limit): 
    a = [True] * limit 
    a[0] = a[1] = False 
    sqrt_limit = int(limit**0.5) + 1 
    predicate = lambda x: x[0] <= sqrt_limit 
    for i, isprime in it.takewhile(predicate, enumerate(a)): 
     if isprime: 
      for n in xrange(i*i, limit, i): 
       a[n] = False 
    return sum(i for i,n in enumerate(a) if n) 

的takewhile功能將停止迭代。 i*i不會給出錯誤，因爲它總是會比limit小。

在我的機器上，它的迭代速度是迭代所有數字的兩倍。

Answer 2

看一看這個相關主題： Fastest way to list all primes below N 最快篩低於8×10^8 rwh_prime1通過@Robert威廉·漢克斯

'''Robert William Hanks 2010''' 
def primes1(n): 
    """ Returns a list of primes < n """ 
    sieve = [True] * (n/2) 
    for i in xrange(3,int(n**0.5)+1,2): 
     if sieve[i/2]: 
      sieve[i*i/2::i] = [False] * ((n-i*i-1)/(2*i)+1) 
    return [2] + [2*i+1 for i in xrange(1,n/2) if sieve[i]]