确定给定范围内的素数

Question

我想用Python来确定指定范围内的所有质数，例如最多 20 个。我有以下代码：

p = [ ]
for i in range(0, 20):
    for x in range(2, i):
        if i%x == 0:
            break
        else:
            p = p + [i]
            break
print p

输出为：

[3, 5, 7, 9, 11, 13, 15, 17, 19]

然而，15 和 9 不是质数。我错过了什么？

Answer 1

else 分支在您找到一个不能被 i 整除的数字时执行。在这种情况下，这意味着要添加 任何奇数 ，因为它们不能被 2 整除，但所有偶数都是。 9 和 15 可能不是质数，但它们是奇数。

只有当 for 循环测试了范围内的所有整数时才应该添加一个数字，而不是当 if 测试失败时。您可以通过 unindenting else 分支来做到这一点，以便它与 for 循环相匹配。

而不是匹配 if:

for ...:
    if ...:
    else:

与for循环匹配：

for ...:
    if ...:
else:

因为只有当 for 循环 而不是 使用 break 语句结束时才会执行，例如当所有数字都经过测试且无法除法时 x:

for i in range(0, 20):
    for x in range(2, i):
        if i%x == 0:
            break
    else:
        p = p + [i]

请注意，break 然后可以从 else 套件中删除，因为到那时您不再处于循环中。

请注意，要找到一个素数，您只需要测试该数的平方根即可；如果 x 可以被数字 i 整除，那么它也可以被 i 的所有约数整除。参见 Why do we check up to the square root of a prime number to determine if it is prime?

并且也可以使用 list.append() 向列表中添加数字，这比在另一个列表中使用加法运算符更清楚一点：

for i in range(20):
    if i < 2:
        continue  # not prime numbers either
    for x in range(2, int(i ** 0.5) + 1):
        if i % x == 0:
            # found a divisor, abort search
            break
    else:
        p.append(i)

演示：

>>> p = []
>>> for i in range(20):
...     if i < 2:
...         continue  # not prime numbers either
...     for x in range(2, int(i ** 0.5) + 1):
...         if i % x == 0:
...             # found a divisor, abort search
...             break
...     else:
...         p.append(i)
... 
>>> p
[2, 3, 5, 7, 11, 13, 17, 19]

确定给定范围内的素数

Determine primes in given range

python

primes