我可以用生成器优化我的素数求和函数吗？
Can I optimize my prime number summing function with generators?
问题：虽然下面的代码有效，但它花费的时间太长，无法找到小于 2,000,000 的所有素数的总和。
过去的尝试： 我曾尝试实施 while 循环、计数器和许多其他工具来修改代码，但它们最终也修改了我的结果。以前，我只是将数字添加到现有变量而不是将它们附加到列表，但结果是一样的。
我相信生成器 function/expression 会解决问题，但我在实现函数、表达式或两者时遇到了问题。
# 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)
上次尝试 生成器 expressions/functions:
#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))
预期结果：我不需要超快处理结果，但我希望它能在一两分钟内处理。
奖励： 对于任何回复的人，如果你也能解释你是如何得出结论的，那对我会有帮助（虽然 "experience" 是一个有效的解释, 它没有帮助)。
我认为关键问题是如何快速且正确地找到所有素数。还有 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
当到达(2, 100000)时，时间成本为：
0.1730230279999887 # this answer
19.639503588000025 # your answer
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 秒来计算总和
此查询的答案归结为您所说的优化。生成器可用于优化 space 用法。你浪费 space 的地方是你主代码中的这个逻辑：
primes.append(i)
你的 is_prime() 功能不会浪费 space。当序列计算可以提前中止而不是完全创建然后部分使用时，生成器只节省 time。这里不是这种情况。
这是一个简单的返工，可以按时间清理您的 is_prime() 实现，并使用 生成器表达式 来避免创建素数列表：
def is_prime(number):
if number <= 2 or number % 2 == 0:
return number == 2
for divisor in range(3, int(number ** 0.5) + 1, 2):
if number % divisor == 0:
return False
return True
result = sum(number for number in range(2, 2_000_000) if is_prime(number))
print(result)
这将在大约 10 秒内完成任务，完全在您的一两分钟限制之内，并且不需要太多代码。它不是最优的 time-wise，只是更好的 time-wise，并且合理优化 space-wise.
重温
生成器还有另一种方法可以提供 time 超出我上面描述的改进。与可以随时传递任何数字的 is_prime() 不同，生成器可以保证它将使用升序数字，因此可以进行简化假设。同样，它可以在调用之间保持状态，这与实现的 is_prime() 不同。让我们通过生成素数来重新解决这个问题：
def prime_generator(limit):
yield 2
number = 3
while number <= limit:
for divisor in range(3, int(number ** 0.5) + 1, 2):
if number % divisor == 0:
break
else: # no break
yield number
number += 2
print(sum(prime_generator(2_000_000)))
尝试使用这种方法的各种安排，它最多比我原来的解决方案提速 5%。
筛子
最后，让我们用筛子来解决这个问题。这种方法比上面的解决方案使用更多 space 来获得时间方面的性能：
def sum_primes(limit): # assumes limit > 1
sieve = [False, False, True] + [True, False] * ((limit - 1) // 2)
number = 3
result = 2
while number <= limit:
if sieve[number]:
result += number
for i in range(number * number, limit + 1, number):
sieve[i] = False
number += 2
return result
print(sum_primes(2_000_000))
这在我的系统上不到 1 秒就完成了素数求和。它比之前基于生成器的解决方案快 15 倍。
首先，我有数学背景。其次，这使用了 Fermant 的 Little Theroem（虽然我不确定这个名字，但我忘记了）。我只是谷歌了一下，花了很多时间编码和调试。在这里！
'''
def is_prime():
a = int(input("Eneter any number"))
for p in range(2, a + 1):
if (a % p == 0):
isprime = 1
for j in range(2, (p // 2 + 1)):
if(p % j == 0):
isprime = 0
break
if (isprime == 1):
print(" %d is a Prime Factor of %d" %(p, a))
is_prime()
'''
祝你有愉快的一天！
get_sum_of_primes_in_range(0, constant_max_value)的结果是一个常量，可以预先计算
get_sum_of_primes_in_range(0, n+x)的结果可以做到get_sum_of_primes_in_range(0, n) + get_sum_of_primes_in_range(n, x)。
通过结合这些东西；对于 n 的选定值，您可以获得 table 的预计算结果，并且只使用处理时间来查找 get_sum_of_primes_in_range(n, x) 部分。
基本上；而不是做 get_sum_of_primes_in_range(0, x)；您可以执行 k = x / 100 和 n = k * 100、result = table[k] + get_sum_of_primes_in_range(n, x) 并跳过大量工作；您希望能够（平均）跳过的工作量取决于您希望table 预计算结果的大小。
对于 get_sum_of_primes_in_range(n, x) 你想要基于 "Sieve of Eratosthenes" 的东西（见 https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes ）。请注意，Eratosthenes 筛法可以使用模数从任意值开始，而不必从 0 开始。
你专注于制作生成器函数就是the XY problem的一个例子。您已经决定解决代码性能问题的方法是使用生成器，但这实际上并不正确。当您得到与生成器无关的答案时，您认为它们没有帮助，而我们其他人只是对为什么生成器首先相关感到有点困惑。
让我们检查一下您遇到性能问题的原因。主要问题是您的代码需要 O(n) 时间来确定每个数字 n 是否为质数。您必须对从两个到您的限制的每个数字执行此操作。这意味着整个算法需要 O(N**2) 时间，其中 N 是要检查的最大数字（例如 200 万）。对于大型 N，您的代码将花费很长时间。
使用素数生成器本身并不能改善这一点。确定每个候选值是否为素数仍然需要同样长的时间，如果您坚持使用当前算法，您仍然需要检查所有相同的数字。充其量就像将素数立即添加到 运行 宁和中一样好，而不是将它们放入列表中并在最后求和。也就是说，它可以节省你的记忆，但不能节省时间。
显着提高性能的真正方法是使用工作量更少的更智能的算法。有很多好方法可以在更短的时间内找到素数。有些可以作为生成器实现，但在这种情况下，一次计算所有素数并使用额外的内存来换取更好的性能可能是一个合理的权衡。
那是因为您的计算机一次可以在内存中保存数十亿个整数。少于几十亿的数字在 Python 中使用大约 28 个字节，因此其中两百万个需要大约 56 MB，加上列表数据结构大约 18 MB。所以你可以做一个内存密集型算法而不需要担心你的内存使用。
这是 Sieve of Eratosthenes algorithm for computing all of the primes less than N in pure Python. The implementation was originally by Robert Williams Hanks in this answer, but this version was tweaked a bit by Bruno Astrolino to work a little more efficiently in Python 3.6+ in this answer.
的一个非常快速的实现
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=100_000 （少了 20 倍）。我不愿意等待三个小时左右的低效算法需要 N=2_000_000.
请注意，如果您真的想要一个出于其他原因产生素数的生成器，the answers to this question 中有一些很好的无限素数生成器实现。使用它们中的任何一个来解决你的求和问题不太可能导致比我上面提供的更快的代码，直到你得到如此大的 N 以至于你不能一次将整个筛子放入内存（并且只有一些生成器会对此有所帮助，有些生成器本身有很大的内存开销。
这是一个使用混合引导方法的生成器。它使用一个（不是特别有效的）筛子来识别平方根以下的素数，在产生它们时将它们存储起来，然后使用这些来试除 n 以下的剩余奇数。对于 n = 2_000_000，它从不存储超过 700 个数字，因此它的内存占用量较小（以更多处理时间为代价）：
import math
def primes(n):
k = 1 + int(math.sqrt(n))
#phase 1: sieve to k
if n >= 2:
yield 2
small_primes = [2]
candidates = [2*i + 1 for i in range(1,(k+1)//2)]
while len(candidates) > 0:
p = candidates[0]
small_primes.append(p)
candidates = [x for x in candidates if x % p != 0]
yield p
#at this stage we have all primes below k
#loop through remaining odd numbers
#dividing by these primes
if k%2 == 0: k +=1
while k <= n:
if all(k%p != 0 for p in small_primes): yield k
k += 2
我没有费心去计时，但 sum(primes(2_000_000)) 大约需要 3 秒。我没有费心计算它的原因是因为我不想让它与 Blckkgght 的代码相比感到尴尬——它显示了非生成器优化筛法的速度有多快。
这是一个非常快速的纯 Python 素数生成器，由 Willy Good 创建，可在评论 here 中找到。就您的特定用例的性能和复杂性而言，这可能有点矫枉过正，但我认为 Python 中的许多 Whosebug prime 都没有意识到这一点。
def primes235(limit):
yield 2; yield 3; yield 5
if limit < 7: return
modPrms = [7,11,13,17,19,23,29,31]
gaps = [4,2,4,2,4,6,2,6,4,2,4,2,4,6,2,6] # 2 loops for overflow
ndxs = [0,0,0,0,1,1,2,2,2,2,3,3,4,4,4,4,5,5,5,5,5,5,6,6,7,7,7,7,7,7]
lmtbf = (limit + 23) // 30 * 8 - 1 # integral number of wheels rounded up
lmtsqrt = (int(limit ** 0.5) - 7)
lmtsqrt = lmtsqrt // 30 * 8 + ndxs[lmtsqrt % 30] # round down on the wheel
buf = [True] * (lmtbf + 1)
for i in xrange(lmtsqrt + 1):
if buf[i]:
ci = i & 7; p = 30 * (i >> 3) + modPrms[ci]
s = p * p - 7; p8 = p << 3
for j in range(8):
c = s // 30 * 8 + ndxs[s % 30]
buf[c::p8] = [False] * ((lmtbf - c) // p8 + 1)
s += p * gaps[ci]; ci += 1
for i in xrange(lmtbf - 6 + (ndxs[(limit - 7) % 30])): # adjust for extras
if buf[i]: yield (30 * (i >> 3) + modPrms[i & 7])
与 Robert William Hanks' 最佳纯 Python 解决方案的速度比较，后者更紧凑且更易于理解：
$ time ./prime_rwh2.py 1e7
664579 primes found < 1e7
real 0m0.883s
user 0m0.266s
sys 0m0.047s
$ time ./prime_wheel.py 1e7
664579 primes found < 1e7
real 0m0.285s
user 0m0.234s
sys 0m0.063s
Willy Good 的解决方案是 mod 30 轮筛，它避免了 2、3 和 5 的 using/storing 倍数，除非手动产生它们以使其完整。它对我来说非常有用，最高可达 2.5e9，其中笔记本电脑中的 8G RAM 已完全用完并且系统崩溃。
问题：虽然下面的代码有效，但它花费的时间太长，无法找到小于 2,000,000 的所有素数的总和。
过去的尝试： 我曾尝试实施 while 循环、计数器和许多其他工具来修改代码，但它们最终也修改了我的结果。以前，我只是将数字添加到现有变量而不是将它们附加到列表，但结果是一样的。
我相信生成器 function/expression 会解决问题，但我在实现函数、表达式或两者时遇到了问题。
# 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)
上次尝试 生成器 expressions/functions:
#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))
预期结果：我不需要超快处理结果，但我希望它能在一两分钟内处理。
奖励： 对于任何回复的人，如果你也能解释你是如何得出结论的，那对我会有帮助（虽然 "experience" 是一个有效的解释, 它没有帮助)。
我认为关键问题是如何快速且正确地找到所有素数。还有 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
当到达(2, 100000)时，时间成本为：
0.1730230279999887 # this answer
19.639503588000025 # your answer
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 秒来计算总和
此查询的答案归结为您所说的优化。生成器可用于优化 space 用法。你浪费 space 的地方是你主代码中的这个逻辑：
primes.append(i)
你的 is_prime() 功能不会浪费 space。当序列计算可以提前中止而不是完全创建然后部分使用时，生成器只节省 time。这里不是这种情况。
这是一个简单的返工，可以按时间清理您的 is_prime() 实现，并使用 生成器表达式 来避免创建素数列表：
def is_prime(number):
if number <= 2 or number % 2 == 0:
return number == 2
for divisor in range(3, int(number ** 0.5) + 1, 2):
if number % divisor == 0:
return False
return True
result = sum(number for number in range(2, 2_000_000) if is_prime(number))
print(result)
这将在大约 10 秒内完成任务，完全在您的一两分钟限制之内，并且不需要太多代码。它不是最优的 time-wise，只是更好的 time-wise，并且合理优化 space-wise.
重温
生成器还有另一种方法可以提供 time 超出我上面描述的改进。与可以随时传递任何数字的 is_prime() 不同，生成器可以保证它将使用升序数字，因此可以进行简化假设。同样，它可以在调用之间保持状态，这与实现的 is_prime() 不同。让我们通过生成素数来重新解决这个问题：
def prime_generator(limit):
yield 2
number = 3
while number <= limit:
for divisor in range(3, int(number ** 0.5) + 1, 2):
if number % divisor == 0:
break
else: # no break
yield number
number += 2
print(sum(prime_generator(2_000_000)))
尝试使用这种方法的各种安排，它最多比我原来的解决方案提速 5%。
筛子
最后，让我们用筛子来解决这个问题。这种方法比上面的解决方案使用更多 space 来获得时间方面的性能：
def sum_primes(limit): # assumes limit > 1
sieve = [False, False, True] + [True, False] * ((limit - 1) // 2)
number = 3
result = 2
while number <= limit:
if sieve[number]:
result += number
for i in range(number * number, limit + 1, number):
sieve[i] = False
number += 2
return result
print(sum_primes(2_000_000))
这在我的系统上不到 1 秒就完成了素数求和。它比之前基于生成器的解决方案快 15 倍。
首先，我有数学背景。其次，这使用了 Fermant 的 Little Theroem（虽然我不确定这个名字，但我忘记了）。我只是谷歌了一下，花了很多时间编码和调试。在这里！
'''
def is_prime():
a = int(input("Eneter any number"))
for p in range(2, a + 1):
if (a % p == 0):
isprime = 1
for j in range(2, (p // 2 + 1)):
if(p % j == 0):
isprime = 0
break
if (isprime == 1):
print(" %d is a Prime Factor of %d" %(p, a))
is_prime()
'''
祝你有愉快的一天！
get_sum_of_primes_in_range(0, constant_max_value)的结果是一个常量，可以预先计算
get_sum_of_primes_in_range(0, n+x)的结果可以做到get_sum_of_primes_in_range(0, n) + get_sum_of_primes_in_range(n, x)。
通过结合这些东西；对于 n 的选定值，您可以获得 table 的预计算结果，并且只使用处理时间来查找 get_sum_of_primes_in_range(n, x) 部分。
基本上；而不是做 get_sum_of_primes_in_range(0, x)；您可以执行 k = x / 100 和 n = k * 100、result = table[k] + get_sum_of_primes_in_range(n, x) 并跳过大量工作；您希望能够（平均）跳过的工作量取决于您希望table 预计算结果的大小。
对于 get_sum_of_primes_in_range(n, x) 你想要基于 "Sieve of Eratosthenes" 的东西（见 https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes ）。请注意，Eratosthenes 筛法可以使用模数从任意值开始，而不必从 0 开始。
你专注于制作生成器函数就是the XY problem的一个例子。您已经决定解决代码性能问题的方法是使用生成器，但这实际上并不正确。当您得到与生成器无关的答案时，您认为它们没有帮助，而我们其他人只是对为什么生成器首先相关感到有点困惑。
让我们检查一下您遇到性能问题的原因。主要问题是您的代码需要 O(n) 时间来确定每个数字 n 是否为质数。您必须对从两个到您的限制的每个数字执行此操作。这意味着整个算法需要 O(N**2) 时间，其中 N 是要检查的最大数字（例如 200 万）。对于大型 N，您的代码将花费很长时间。
使用素数生成器本身并不能改善这一点。确定每个候选值是否为素数仍然需要同样长的时间，如果您坚持使用当前算法，您仍然需要检查所有相同的数字。充其量就像将素数立即添加到 运行 宁和中一样好，而不是将它们放入列表中并在最后求和。也就是说，它可以节省你的记忆，但不能节省时间。
显着提高性能的真正方法是使用工作量更少的更智能的算法。有很多好方法可以在更短的时间内找到素数。有些可以作为生成器实现，但在这种情况下，一次计算所有素数并使用额外的内存来换取更好的性能可能是一个合理的权衡。
那是因为您的计算机一次可以在内存中保存数十亿个整数。少于几十亿的数字在 Python 中使用大约 28 个字节，因此其中两百万个需要大约 56 MB，加上列表数据结构大约 18 MB。所以你可以做一个内存密集型算法而不需要担心你的内存使用。
这是 Sieve of Eratosthenes algorithm for computing all of the primes less than N in pure Python. The implementation was originally by Robert Williams Hanks in this answer, but this version was tweaked a bit by Bruno Astrolino to work a little more efficiently in Python 3.6+ in this answer.
的一个非常快速的实现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=100_000 （少了 20 倍）。我不愿意等待三个小时左右的低效算法需要 N=2_000_000.
请注意，如果您真的想要一个出于其他原因产生素数的生成器，the answers to this question 中有一些很好的无限素数生成器实现。使用它们中的任何一个来解决你的求和问题不太可能导致比我上面提供的更快的代码，直到你得到如此大的 N 以至于你不能一次将整个筛子放入内存（并且只有一些生成器会对此有所帮助，有些生成器本身有很大的内存开销。
这是一个使用混合引导方法的生成器。它使用一个（不是特别有效的）筛子来识别平方根以下的素数，在产生它们时将它们存储起来，然后使用这些来试除 n 以下的剩余奇数。对于 n = 2_000_000，它从不存储超过 700 个数字，因此它的内存占用量较小（以更多处理时间为代价）：
import math
def primes(n):
k = 1 + int(math.sqrt(n))
#phase 1: sieve to k
if n >= 2:
yield 2
small_primes = [2]
candidates = [2*i + 1 for i in range(1,(k+1)//2)]
while len(candidates) > 0:
p = candidates[0]
small_primes.append(p)
candidates = [x for x in candidates if x % p != 0]
yield p
#at this stage we have all primes below k
#loop through remaining odd numbers
#dividing by these primes
if k%2 == 0: k +=1
while k <= n:
if all(k%p != 0 for p in small_primes): yield k
k += 2
我没有费心去计时，但 sum(primes(2_000_000)) 大约需要 3 秒。我没有费心计算它的原因是因为我不想让它与 Blckkgght 的代码相比感到尴尬——它显示了非生成器优化筛法的速度有多快。
这是一个非常快速的纯 Python 素数生成器，由 Willy Good 创建，可在评论 here 中找到。就您的特定用例的性能和复杂性而言，这可能有点矫枉过正，但我认为 Python 中的许多 Whosebug prime 都没有意识到这一点。
def primes235(limit):
yield 2; yield 3; yield 5
if limit < 7: return
modPrms = [7,11,13,17,19,23,29,31]
gaps = [4,2,4,2,4,6,2,6,4,2,4,2,4,6,2,6] # 2 loops for overflow
ndxs = [0,0,0,0,1,1,2,2,2,2,3,3,4,4,4,4,5,5,5,5,5,5,6,6,7,7,7,7,7,7]
lmtbf = (limit + 23) // 30 * 8 - 1 # integral number of wheels rounded up
lmtsqrt = (int(limit ** 0.5) - 7)
lmtsqrt = lmtsqrt // 30 * 8 + ndxs[lmtsqrt % 30] # round down on the wheel
buf = [True] * (lmtbf + 1)
for i in xrange(lmtsqrt + 1):
if buf[i]:
ci = i & 7; p = 30 * (i >> 3) + modPrms[ci]
s = p * p - 7; p8 = p << 3
for j in range(8):
c = s // 30 * 8 + ndxs[s % 30]
buf[c::p8] = [False] * ((lmtbf - c) // p8 + 1)
s += p * gaps[ci]; ci += 1
for i in xrange(lmtbf - 6 + (ndxs[(limit - 7) % 30])): # adjust for extras
if buf[i]: yield (30 * (i >> 3) + modPrms[i & 7])
与 Robert William Hanks' 最佳纯 Python 解决方案的速度比较，后者更紧凑且更易于理解：
$ time ./prime_rwh2.py 1e7
664579 primes found < 1e7
real 0m0.883s
user 0m0.266s
sys 0m0.047s
$ time ./prime_wheel.py 1e7
664579 primes found < 1e7
real 0m0.285s
user 0m0.234s
sys 0m0.063s
Willy Good 的解决方案是 mod 30 轮筛，它避免了 2、3 和 5 的 using/storing 倍数，除非手动产生它们以使其完整。它对我来说非常有用，最高可达 2.5e9，其中笔记本电脑中的 8G RAM 已完全用完并且系统崩溃。