如何仅在第一次遇到素数时追加到列表

Question

我写了下面的Python代码来打印1000之前的所有素数:

primes = []
for prime in xrange(1, 1000):
    for b in xrange(2, prime):
        if (prime % b == 0):
            break
        else:
            primes.append(prime)
print primes

然而，如果一个数字是素数，在移动到下一个数字之前，它被附加了很多次。我尝试使用continue而不是break，但这不起作用。

我还在上面添加了一些代码(可以工作)，以便简单地将数组输出到文本文件中。它太大了，我甚至不能把它粘贴到这里。

如何将每个素数只添加一次而不是多次?

Answer 1

您可以在这里非常有效地使用Python中的一个特性。只需要像这样改变缩进:

primes = []
for prime in xrange(1, 1000):
    for b in xrange(2, prime):
        if (prime % b == 0):
            break
    else:
        primes.append(prime)
print primes

即取消else子句的缩进。这样，它就不是if的else，而是for循环的CC_4。for循环可以有一个else分支，该分支在循环执行了所有预定的迭代之后执行。如果有一个break被调用，它不会被执行。

你可以在这里使用它，而不需要修改很多原始代码。

当然，在您的原始版本中，每次循环迭代中，如果测试的数字不是非素数，则该测试的数字被附加(这不是您想要的)。

还要注意1不是质数(至少从1801年高斯开始，有人说甚至从欧几里得(公元前600年)第一次写质数开始，尽管从19世纪开始就有异教徒)，所以你的外部循环应该从2开始。

但是请注意Daniel在他的回答中写了什么;你不需要一直走到prime，因为在到达prime的平方根后，你可以跳出来。我总是比较b * b和prime，但也许计算sqrt(prime)一次甚至更快。

当然，你可以通过完全忽略所有偶数来更快。-)

Answer 2

只有当数字到达循环末尾而没有找到除数时，才需要添加数字。

from math import sqrt
prime = True
for b in xrange(2, sqrt(prime)):
    if prime % b == 0:
        prime = False
        break
if prime:
    primes.append(prime)

注意:我已经添加了一个优化:你只需要测试一个数字的平方根，因为在那之后的任何东西都不可能被除法。