怎样才能使素数的求和更快呢？

Question

def is_prime(x):
    if x<2:
        return False
    elif x%2==0:
        if x==2:
            return True
        else:
            return False
    else:
        for i in range(3,x+1,2):
            if x%i==0 and i==x:
                return True
                break
            elif x%i==0:
                return False
                break


def sum_primes(m):
    total=0
    for i in range (3,m,2):
        if is_prime(i):
            total+=i
    return total+2

print sum_primes(2000000)

我正在尝试解决一个Project-Euler问题，这个程序可以工作，但它需要太多的时间来给我答案。我怎么才能让它更快，伙计们？

Answer 1

这个问题以前已经问过了：

• python sum of primes
• Optimization of prime number code
• https://codereview.stackexchange.com/questions/37550/summation-of-primes-takes-forever

上面的链接中列出了多种方法。您可能还会发现此链接很有帮助：

• http://www.parallelpython.com/content/view/17/31/

您还可以考虑尝试使用Cython对其进行优化。

Answer 2

Eratosthenes的筛子枚举素数，sum累加它们；首先列出从2到n的数字列表，将它们标记为素数，然后按顺序扫描列表，在每个素数处停止以标记其倍数组合，按顺序收集素数。

function sumPrimes(n) # sum of primes less than n
    sum, sieve := 0, makeArray(2..n, True)
    for p from 2 to n
        if sieve[p]
            sum := sum + p
            for i from p*p to n step p
                sieve[i] = False
    return sum

我会让你把它翻译成Python。

如果你对质数编程感兴趣，我在我的博客上谦虚地推荐this essay。