素数问题

davidmou

# 10 以内的素数之和是：2 + 3 + 5 + 7 = 17，那么请编写程序，计算 2000000 以内的素数之和？
def is_prame(number):
    a = 0
    if number == 2:
        return True
    for each in range(2, number):
        if number % each == 0:
            return False
        else:
            a +=1
            if a == (number - 2):
                return True

def fun():
    count = 2
    while 1:
        if is_prame(count):
            yield count
            count += 1
        else:
            count += 1

sumcount = 0
for eachbody in fun():
    sumcount += eachbody
    if eachbody == 4:
        break
   
print(sumcount)

为什么这个代码执行后，很久都没有结果（没显示错误）
请大神指教

            

isdkz

问题出在is_prime函数中的for循环上。当前的代码会对每个数字都进行从2到number的遍历，这样的复杂度为O(n)，会导致程序执行时间过长。我们可以对该循环进行优化，只需要遍历到number的平方根即可。

以下是修改后的代码：

1. import math
   
2. 
   
3. def is_prime(number):
   
4.     if number == 2:
   
5.         return True
   
6.     if number % 2 == 0 or number == 1:
   
7.         return False
   
8.     for each in range(3, int(math.sqrt(number)) + 1, 2):
   
9.         if number % each == 0:
   
10.             return False
    
11.     return True
    
12. 
    
13. def fun():
    
14.     count = 2
    
15.     while count < 2000000:
    
16.         if is_prime(count):
    
17.             yield count
    
18.         count += 1
    
19. 
    
20. sumcount = 0
    
21. for eachbody in fun():
    
22.     sumcount += eachbody
    
23. 
    
24. print(sumcount)
    

复制代码

这个修改后的代码会更高效地计算2000000以内的素数之和。

学习编程中的Ben

问题分析

你的代码逻辑存在一些问题，导致程序无法正确计算出2000000以内的素数之和。下面是对代码中存在问题的分析：

1. 缩进错误：你的代码中缩进存在问题，这会导致代码无法正确执行。

2. 判断质数的逻辑错误：在is_prime()函数中，你使用了一个循环来判断一个数字是否为质数。然而，你在循环中累加变量a的目的不太清晰，并且在判断质数时存在逻辑错误。

3. 循环控制错误：在fun()生成器函数中，你设置了一个死循环，但在循环体内没有退出循环的条件，这会导致程序无限运行。

4. 范围错误：你在生成素数的过程中，只处理到了第一个素数4，然后就中断了循环，没有计算2000000以内的素数之和。

修正代码

下面是修正后的代码，解决了以上提到的问题，并计算出2000000以内的素数之和。

1. def is_prime(number):
2.     if number == 2:
3.         return True
4.     for each in range(2, int(number ** 0.5) + 1):
5.         if number % each == 0:
6.             return False
7.     return True
9. def fun():
10.     count = 2
11.     while count <= 2000000:
12.         if is_prime(count):
13.             yield count
14.         count += 1
16. sum_count = 0
17. for prime in fun():
18.     sum_count += prime
20. print(sum_count)

复制代码

修正后的代码使用了根号n的优化方法，将判断质数的范围缩小至2到√n。此外，修改了循环结构，使得循环在2000000以内进行，并逐个计算素数之和。

请注意，在计算2000000以内的素数之和时，程序需要一些时间才能完成运算。因此，在执行时可能会稍微等待一段时间。如果你希望加快计算速度，可以使用更高效的算法来计算素数之和。

希望这次的解答能解决你的问题！如果还有其他疑问，请随时提出。

如果回答对你有帮助，请给我一个最佳答案！

ba21

计算 2000000 以内的素数之和的最高效代码可以使用埃拉托斯特尼筛法（Sieve of Eratosthenes）。这种算法能够快速地找出一定范围内的所有素数。

以下是一个使用埃拉托斯特尼筛法计算 2000000 以内素数之和的 Python 程序示例：

1. def prime_sum(limit):
   
2.     is_prime = [True] * (limit+1)
   
3.     is_prime[0] = is_prime[1] = False
   
4. 
   
5.     p = 2
   
6.     while p * p <= limit:
   
7.         if is_prime[p]:
   
8.             for i in range(p * p, limit+1, p):
   
9.                 is_prime[i] = False
   
10.         p += 1
    
11. 
    
12.     prime_sum = sum(i for i, prime in enumerate(is_prime) if prime)
    
13. 
    
14.     return prime_sum
    
15. 
    
16. limit = 2000000
    
17. sum_of_primes = prime_sum(limit)
    
18. print(sum_of_primes)

复制代码

在这个程序中，我们首先创建了一个布尔数组 is_prime，用于表示每个数字是否是素数。初始时，我们将数组中所有的元素都设置为 True，表示所有数字都是素数。然后，我们将数组的第一个元素和第二个元素（0 和 1）设置为 False，因为它们不是素数。

接下来，我们从 2 开始遍历到平方根为止，将所有的倍数标记为非素数。如果一个数字 p 是素数，那么它的倍数 p*p, p*p+p, p*p+2p, ... 都不是素数。我们通过将这些倍数在 is_prime 数组中标记为 False 来实现。

最后，我们通过求和操作计算出数组中所有为 True 的索引值，并将结果返回为素数之和。

运行程序，输出结果为：

1. 
   
2. 142913828922

复制代码

这表示 2000000 以内的素数之和为 142913828922。

使用埃拉托斯特尼筛法的时间复杂度为 O(n log log n)，因此它是一种高效的方法来计算一定范围内的素数之和。

陶远航

您好，我很高兴您对素数之和感兴趣。

您的代码执行后没有结果的原因是您的循环条件没有设置正确。您的代码中，您使用了一个生成器函数fun()来产生素数，然后在一个for循环中累加这些素数，直到遇到4为止。但是，4不是一个素数，所以您的生成器函数永远不会产生4，导致您的for循环无法终止。这就是为什么您的代码一直在运行，但没有输出任何结果。

如果您想计算2000000以内的素数之和，您需要修改您的代码，让循环条件变成当生成的素数小于或等于2000000时继续循环，否则跳出循环。例如，您可以这样写：

1. def is_prame(number):
   
2.     a = 0
   
3.     if number == 2:
   
4.         return True
   
5.     for each in range(2, number):
   
6.         if number % each == 0:
   
7.             return False
   
8.         else:
   
9.             a +=1
   
10.             if a == (number - 2):
    
11.                 return True
    
12. 
    
13. def fun():
    
14.     count = 2
    
15.     while 1:
    
16.         if is_prame(count):
    
17.             yield count
    
18.             count += 1
    
19.         else:
    
20.             count += 1
    
21. 
    
22. sumcount = 0
    
23. for eachbody in fun():
    
24.     if eachbody <= 2000000: # 修改了这里的条件
    
25.         sumcount += eachbody
    
26.     else:
    
27.         break # 添加了这里的跳出语句
    
28.    
    
29. print(sumcount)

复制代码

这样的话，您的代码就可以正确地输出结果了。但是，这种方法还是比较低效的，因为它需要对每个数都进行素数判断。如果您想提高效率，您可以使用一种叫做埃拉托斯特尼筛法（Sieve of Eratosthenes）的算法。这种算法可以快速地找出一定范围内的所有素数，并且可以用Python实现。我建议您参考一下网页上的内容，学习一下这种算法的原理和实现方法。

希望我的回答对您有帮助。如果您还有其他问题或想法，请随时与我分享。