Python筛素数

Question

我试图用Python2.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

看看这个相关的主题： Fastest way to list all primes below N 在8*10^8以下的最快筛子是由@Robert William Hanks编码的rwh峎u prime1

'''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]]

Answer 2

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

它应该是：

^{pr2}$

或者，更有效地：

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

因为否则，当i实际上是一个素数时，就会将i设置为非素数。 （筛子应该将i的所有倍数标记为非素数，除了i本身！）在

---

请注意，您正在迭代所有的数字，直到limit，但是您可以在到达sqrt(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函数将在到达limit的平方根后立即停止迭代。i*i不会出错，因为它总是小于limit。在

在我的机器上，它的速度是迭代所有数字的两倍。在