求大素数的和需要时间！如何提高效率？

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

使用Eratosthenes筛：

$ 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

在我的机器上大约四分之一秒。你知道吗

Answer 3

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()中将偶数作为特例处理，然后只处理奇数除数。使用理解或生成器表达式会将更多循环代码下推到C级别，通常会使您的速度更快一些。你知道吗