对大质数求和需要时间！我怎样才能让它更有效率？

Question

我正在尝试完成 Project Euler's 10th problem，但我目前的代码花费了太多时间，无法完成。

我环顾四周，但没能找到如何缩短代码运行时间的方法。

这是我的代码：

def IsPrime(num):
    for i in range(2, num/2):
        if num % i == 0:
            prime = False
            return prime
    prime = True
    return prime

def SumOfPrime(limit):
    primesum=2+3    #For some reason my prime finder doesn't allow numbers below 5
    for check in range(5,limit):
        prime=IsPrime(check)
        if prime == True:
            primesum += check
    return primesum^2

print(SumOfPrime(2000000))

正确答案应该是 142913828922，但是，如前所述，我没有得到完整的输出。有什么办法可以使这段代码更快？

Answer 1

加快实施速度的一些技巧：

您只需要检查除数直到一个数的平方根，两个数的乘积越大，结果就越大。
您也可以只搜索质因数，也许将找到的质数添加到列表或类似的东西中。

如果你想要更高效的算法，请查看https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

Answer 2

now it takes 32.98 sec for it to finish. I'd love to see a faster algorithm

您应该使用埃拉托色尼筛。忽略这一点，这次返工应该让你的时间不到 10 秒：

def isPrime(number):
    if number <= 2:
        return number == 2

    if number % 2 == 0:
        return False

    for divisor in range(3, int(number ** 0.5) + 1, 2):
        if number % divisor == 0:
            return False

    return True

def sumOfPrimes(limit):
    return sum(number for number in range(limit) if isPrime(number))

print(sumOfPrimes(2000000))

将偶数数作为isPrime()中的特例处理，然后只处理奇数除数。使用 comprehension 或 generator expression 将更多的循环代码推到 C 级别并且通常会让你速度快一点。

Answer 3

使用埃拉托色尼筛法：

$ python
Python 2.7.13 (default, Mar 13 2017, 20:56:15)
[GCC 5.4.0] on cygwin
Type "help", "copyright", "credits" or "license" for more information.
>>> def sumPrimes(n):
...     i, p, ps, m, sum = 0, 3, [2], n // 2, 2
...     sieve = [True] * m
...     while p <= n:
...         if sieve[i]:
...             sum += p
...             for j in range((p*p-3)/2, m, p):
...                 sieve[j] = False
...         i, p = i+1, p+2
...     return sum
...
>>> from time import time
>>> start = time(); print sumPrimes(2000000); print time() - start
142913828922
0.262000083923

在我的机器上大约四分之一秒。

对大质数求和需要时间！我怎样才能让它更有效率？

Summing large primes takes time! How do I make it more efficient?

python

primes