我能用生成器优化素数求和函数吗？

Question

问题：当下面的代码工作时，要找到2000000以下的所有素数之和需要花费太长的时间。你知道吗

过去的尝试：我曾尝试实现while循环、计数器和许多其他工具来修改代码，但它们最终也修改了我的结果。以前，我只是简单地将数字添加到现有变量中，而不是将它们附加到列表中，但结果是相同的。你知道吗

我相信生成器函数/表达式可以解决这个问题，但我在实现函数、表达式或两者都有困难。

# Prime number determiner 
def is_prime(x):
    for i in range(2, x-1):
        if x % i == 0:
            return False
    else:
        return True

# Function summing all prime numbers between 2 and 2,000,000
for i in range(2, 2000000):
    if is_prime(i) is True:
        primes.append(i)
results = sum(primes)
print(primes)

上一次尝试生成器表达式/函数：

#Generator version of above
def is_prime_gen(x):
     yield (i for i in range(2, x-1) if x % i == 0)
sum_prime += (j for j in range(2, 2000000) if is_prime_gen(j))

预期结果：我不需要快速处理结果，但我希望它能在一两分钟内处理完毕。你知道吗

好处：对于任何回复的人，如果你能解释一下你是如何得出结论的，那将对我很有帮助（虽然“经验”是一个有效的解释，但它没有帮助）。你知道吗

Answer 1

生成生成器函数的重点是the XY problem。您已经决定使用生成器来解决代码的性能问题，但这实际上是不正确的。当你得到与生成器无关的答案时，你会认为它们没有帮助，而我们其他人只是有点困惑，为什么生成器首先是相关的。你知道吗

让我们检查一下为什么会出现性能问题。主要问题是代码需要O(n)时间来确定每个数n是否为素数。你必须这样做，从两个数字到你的极限是什么。这意味着整个算法需要O(N**2)时间，其中N是要检查的最大数（例如200万）。对于一个大的N您的代码将需要很长时间。你知道吗

为素数使用生成器本身并不能改善这一点。如果每个候选值都是素数，则仍然需要花费同样长的时间来确定，如果您坚持使用当前的算法，则仍然需要检查所有相同的数字。充其量就是把素数立即加到一个连续的和中，而不是把它们放到一个列表中，最后求和。也就是说，它可以节省你的记忆，但不是时间。你知道吗

真正能够大大提高性能的方法是使用一种更智能的算法，它只需较少的工作。有很多好方法可以在更短的时间内找到素数。有些可以实现为生成器，但在这种情况下，一次计算所有素数并使用额外内存来交换更好的性能可能是一种合理的权衡。你知道吗

这是因为你的计算机一次可以在内存中保存数十亿个整数。在Python中，小于数十亿的数字使用大约28个bye，因此其中200万个需要大约56mb，另外列表数据结构需要大约18mb。所以你可以做一个内存密集型算法，而不需要担心你的内存使用。你知道吗

下面是Sieve of Eratosthenes算法的一个非常快速的实现，用于计算纯Python中所有小于N的素数。这个实现最初是由this answer中的Robert Williams Hanks实现的，但是这个版本被Bruno Astrolino稍微调整了一下，以便在this answer中的python3.6+中更有效地工作。你知道吗

from itertools import compress

def rwh_primes1v1(n):
    """ Returns  a list of primes < n for n > 2 """
    sieve = bytearray([True]) * (n//2)
    for i in range(3,int(n**0.5)+1,2):
        if sieve[i//2]:
            sieve[i*i//2::i] = bytearray((n-i*i-1)//(2*i)+1)
    return [2,*compress(range(3,n,2), sieve[1:])]

您需要运行sum(rwh_primes1v1(2_000_000))。在我的计算机上，这大约需要30毫秒，而你的代码需要30秒（长1000倍），N=100000（一个界限要少20倍）。我不愿意等三个小时左右，效率低下的算法需要N=2000000。你知道吗

请注意，如果您真的需要一个生成素数的生成器，那么the answers to this question中有一些很好的无限素数生成器实现。使用它们中的任何一个来解决求和问题都不太可能产生比我上面提供的代码更快的代码，除非你得到一个如此大的N，以至于你不能一次在内存中容纳整个筛选（只有一些生成器会有帮助，一些生成器本身有很大的内存开销）。你知道吗

Answer 2

我认为关键的问题是如何快速而正确地找到所有的素数。关于它有many answers。我发现一个如下：

def isprime(n):
    """Returns True if n is prime."""
    if n == 2:
        return True
    if n == 3:
        return True
    if n % 2 == 0:
        return False
    if n % 3 == 0:
        return False

    i = 5
    w = 2

    while i * i <= n:
        if n % i == 0:
            return False

        i += w
        w = 6 - w

    return True

sum = 0
for n in range(2, 20000):
    if isprime(n):
        sum += n

在范围（2，10000）内时，时间成本为：

0.0043639220002660295  # this answer
0.25401434600007633  # your answer

对于（210000），时间成本为：

0.1730230279999887  # this answer
19.639503588000025  # your answer

Answer 3

import time
prime = (i for i in range(2, 2000000) if is_prime(i))

def is_prime(num):
    if num == 2:
        return True
    if num == 3:
        return True
    if num % 2 == 0:
        return False
    if num % 3 == 0:
        return False

    i = 5
    w = 2

    while i * i <= num:
        if num % i == 0:
            return False

        i += w
        w = 6 - w

    return True

print(sum(prime))
print(time.perf_counter())

我不是专家，但我认为这应该是工作和相当简单的理解。 我使用了ToughMind共享的改进功能。我的系统需要15.5秒来计算总和