1

我正在制作一个 python 程序，它将生成一个数字的质数之和，但该程序没有给出正确的结果，请告诉我为什么。

b=1
#generates a list of numbers.
while b<100:
    b=b+1
    x = 0.0
    a = 0
    d = 0
    #generates a list of numbers less than b. 
    while x<b:
        x=x+1
        #this will check for divisors. 
        if (b/x)-int(b/x) == 0.0:
            a=a+1
        if a==2:
            #if it finds a prime it will add it.
            d=d+b
print d

我让它成功生成了一个素数列表，但我无法添加素数。

这是我用来生成素数列表的代码。

b=1
while b<1000:
    b=b+1
    n = b
    x = 0.0
    a = 0
    while x<n:
        x=x+1
        if (n/x)-int(n/x) == 0.0:
            a=a+1
    if a==2:
        print b
4

6 回答 6

5

在外循环的每次迭代期间，您的d变量都会被重置。将初始化移出该循环。

此外，a == 2检查应该只在外循环的每次迭代中发生一次。将其移出内循环。

b=1
d = 0
#generates a list of numbers.
while b<100:
    b=b+1
    x = 0.0
    a = 0
    #generates a list of numbers less than b. 
    while x<b:
        x=x+1
        #this will check for divisors. 
        if (b/x)-int(b/x) == 0.0:
            a=a+1
    if a==2:
        #if it finds a prime it will add it.
        d=d+b
print d

结果：

1060

当我们这样做的时候，让我们试着清理一下代码，这样它就更容易理解了。你可以把内循环移到它自己的函数中，这样读者可以更清楚地理解它的用途：

def is_prime(b):
    x = 0.0
    a = 0
    while x<b:
        x=x+1
        #this will check for divisors. 
        if (b/x)-int(b/x) == 0.0:
            a=a+1
    if a==2:
        return True
    else:
        return False

b=1
d=0
#generates a list of numbers.
while b<100:
    b=b+1
    if is_prime(b):
        d=d+b
print d

使用描述它们所代表的变量名称也很有用：

def is_prime(number):
    candidate_factor = 0
    amount_of_factors = 0
    while candidate_factor<number:
        #A += B is equivalent to A = A + B
        candidate_factor += 1
        #A little easier way of testing whether one number divides another evenly
        if number % candidate_factor == 0:
            amount_of_factors += 1
    if amount_of_factors == 2:
        return True
    else:
        return False

number=1
prime_total=0
#generates a list of numbers.
while number<100:
    number += 1
    if is_prime(number):
        prime_total += number
print prime_total

for循环比while增加计数器的循环更符合规范：

def is_prime(number):
    amount_of_factors = 0
    for candidate_factor in range(1, number+1):
        if number % candidate_factor == 0:
            amount_of_factors += 1
    if amount_of_factors == 2:
        return True
    else:
        return False

prime_total=0
#generates a list of numbers.
for number in range(2, 101):
    if is_prime(number):
        prime_total += number
print prime_total

如果你觉得大胆，你可以使用列表推导来减少你使用的循环数量：

def is_prime(number):
    factors = [candidate_factor for candidate_factor in range(1, number+1) if number % candidate_factor == 0]
    return len(factors) == 2

#generates a list of numbers.
primes = [number for number in range(2, 101) if is_prime(number)]
prime_total = sum(primes)
print prime_total
于 2013-06-20T20:13:42.103 回答
3

凯文正确回答了你提出的问题。请允许我回答您没有问但应该有的问题：计算小于n的素数之和的最佳方法是什么。答案是使用筛子：

def sumPrimes(n):
    sum = 0
    sieve = [True] * (n+1)
    for p in range(2, n):
        if sieve[p]:
            sum += p
            for i in range(p*p, n, p):
                sieve[i] = False
    return sum

这段代码实现了埃拉托色尼筛法，对素数求和。它的工作原理是重复选择最小的未交叉数（上面代码中的psieve[p] ，当is时选择True），然后删除它的所有倍数（上面代码中的i，增加p以计算 p 的倍数）从它的正方形（因为所有较小的复合材料都已被划掉）。函数的示例使用是print sumPrimes(100)，它打印 1060，这是正确的答案。

请注意，罗兰的答案没有实现埃拉托色尼筛法，尽管他声称它确实如此；使用模函数是罗兰的答案使用试除法，而不是埃拉托色尼筛法的赠品。

如果你对使用素数编程感兴趣，我在我的博客上谦虚地推荐这篇文章。

于 2013-06-21T01:40:06.053 回答
1

如果您这样做是为了学习 python，那么可以使用更简洁（>> 不易出错）的方式来执行此操作。根据您的问题，我假设您正在尝试对以下所有质数求和，包括 100：

sum=0
limit=100
for n in range(2,limit+1):
  if all(n % i for i in range(2, n)):
    sum += n
print sum

印刷1060

于 2013-06-20T20:12:57.533 回答
1

列表推导是 Python 中一个强大的工具。将它们视为类固醇中的 for 循环。:-) 您可以使用它们来实现试除法，这是一种查找素数的简单方法。

它是这样工作的：

In [4]: sum(prime_list(100))
Out[4]: 1061

prime_list功能：

def prime_list(num):
    """Returns a list of all prime numbers up to and including num.
    Based on trial division.

    :num: highest number to test
    :returns: a list of primes up to num

    """
    if num < 3:
        raise ValueError('this function only accepts arguments > 2')
    candidates = range(3, num+1, 2) # (a)
    L = [c for c in candidates if all(c % p != 0 for p in range(3, c, 2))] #(b)
    return [1, 2] + L

现在解释一下。除 2 外，所有素数都是奇数。所以从 3 到（在这种情况下为 100）的所有奇数num都是素数的候选者。让我们生成一个在 (a) 处完成的列表：

In [5]: num = 100

In [6]: range(3, num+1, 2)
Out[6]: [3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 55, 57, 59, 61, 63, 65, 67, 69, 71, 73, 75, 77, 79, 81, 83, 85, 87, 89, 91, 93, 95, 97, 99]

要使奇数c成为质数，必须确保对c所有先前奇数取模后p必须为非零。假设c是25。

In [7]: c = 25

然后p在：

In [8]: range(3, c, 2)
Out[8]: [3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23]

现在检查c模数p：

In [9]: [c % p != 0 for p in range(3, c, 2)]
Out[9]: [True, False, True, True, True, True, True, True, True, True, True]

我们知道 25 % 5 == 0，所以列表中的第二项是False. 但是，要使一个数成为素数，列表中的所有项目都必须为真：

In [10]: all(c % p != 0 for p in range(3, c, 2))
Out[10]: False

所以 25 不是素数。

让我们再试一次c是 41：

In [11]: c = 41

In [12]: range(3, c, 2)
Out[12]: [3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39]

In [13]: [c % p != 0 for p in range(3, c, 2)]
Out[13]: [True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True]

In [14]: all(c % p != 0 for p in range(3, c, 2))
Out[14]: True

确实，41 是一个素数。

所以 prime_list 返回一个素数列表：

In [15]: prime_list(100)
Out[15]: [1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

总结一下，我们简单地使用这个sum()函数：

In [16]: sum(prime_list(100))
Out[16]: 1061

编辑：根据评论，我尝试了 WillNess 建议的改进和使用集合的真正筛子：

def prime_list(num):
    if num < 3:
        raise ValueError('this function only accepts arguments > 2')
    candidates = range(3, num+1, 2)
    L = [c for c in candidates if all(c % p != 0 for p in range(3, c, 2))]
    return [1, 2] + L

def prime_list2(num):
    if num < 3:
        raise ValueError('this function only accepts arguments > 2')
    candidates = range(3, num+1, 2)
    L = [c for c in candidates if all(c % p != 0 for p in
         range(3, int(math.sqrt(c))+1, 2))]
    return [1, 2] + L

def prime_list3(num):
    candidates = set(range(3, num+1, 2))
    results = [1, 2]
    while candidates:
        t = list(candidates)[0]
        results.append(t)
        candidates -= set(range(t, num+1, t))
    return results

一些时间num=100：

In [8]: %timeit prime_list(100)
1000 loops, best of 3: 180 us per loop

In [9]: %timeit prime_list2(100)
1000 loops, best of 3: 192 us per loop

In [10]: %timeit prime_list3(100)
10000 loops, best of 3: 83.9 us per loop

并且num=1000：

In [11]: %timeit prime_list(1000)
100 loops, best of 3: 8.05 ms per loop

In [12]: %timeit prime_list2(1000)
100 loops, best of 3: 2.43 ms per loop

In [13]: %timeit prime_list3(1000)
1000 loops, best of 3: 1.26 ms per loop

num = 5000：

In [14]: %timeit prime_list(5000)
1 loops, best of 3: 166 ms per loop

In [15]: %timeit prime_list2(5000)
100 loops, best of 3: 11.1 ms per loop

In [16]: %timeit prime_list3(5000)
100 loops, best of 3: 15.3 ms per loop

最后num=50000：

In [18]: %timeit prime_list3(50000)
1 loops, best of 3: 1.49 s per loop

In [19]: %timeit prime_list2(50000)
1 loops, best of 3: 170 ms per loop
于 2013-06-20T20:39:34.720 回答
0

只需使用用于生成列表的代码对列表求和：

d = sum(d)
print d
于 2013-06-20T20:00:44.120 回答
0 
def sum_of_prime(num):
        if num < 2:
            return 'Please enter values greater than 2'
        if num == 2:
                return 2
        sum = 0
        for j in range(2,num):
                for i in range(2,j):
                        if (j % i) == 0:
                                break
                else:
                        print j
                        sum = sum + j
        return sum
num = int(raw_input())
result = sum_of_prime(num)
print result
于 2016-06-01T12:42:06.937 回答