1

我正在尝试使用 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
4

2 回答 2

2

看看这个相关主题： 列出 N 以下所有素数的最快方法 8 * 10^8 以下的最快筛子是由@Robert William Hanks 编码的 rwh_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]]
于 2013-09-22T14:28:22.457 回答
2 
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)：

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.

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

于 2013-07-21T14:35:15.423 回答