素数问题

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的平方根即可。

以下是修改后的代码：

import math

def is_prime(number):
    if number == 2:
        return True
    if number % 2 == 0 or number == 1:
        return False
    for each in range(3, int(math.sqrt(number)) + 1, 2):
        if number % each == 0:
            return False
    return True

def fun():
    count = 2
    while count < 2000000:
        if is_prime(count):
            yield count
        count += 1

sumcount = 0
for eachbody in fun():
    sumcount += eachbody

print(sumcount)

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

学习编程中的Ben

问题分析

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

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

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

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

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

修正代码

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

def is_prime(number):    if number == 2:        return True    for each in range(2, int(number ** 0.5) + 1):        if number % each == 0:            return False    return Truedef fun():    count = 2    while count <= 2000000:        if is_prime(count):            yield count        count += 1sum_count = 0for prime in fun():    sum_count += primeprint(sum_count)

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

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

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

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

ba21

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

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

def prime_sum(limit):
    is_prime = [True] * (limit+1)
    is_prime[0] = is_prime[1] = False

    p = 2
    while p * p <= limit:
        if is_prime[p]:
            for i in range(p * p, limit+1, p):
                is_prime[i] = False
        p += 1

    prime_sum = sum(i for i, prime in enumerate(is_prime) if prime)

    return prime_sum

limit = 2000000
sum_of_primes = prime_sum(limit)
print(sum_of_primes)

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

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

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

运行程序，输出结果为：

142913828922

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

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

陶远航

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

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

如果您想计算2000000以内的素数之和，您需要修改您的代码，让循环条件变成当生成的素数小于或等于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():
    if eachbody <= 2000000: # 修改了这里的条件
        sumcount += eachbody
    else:
        break # 添加了这里的跳出语句
   
print(sumcount)

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

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