Python 初学者的循环（寻找素数）

Question

我刚开始学Python，所以对很多东西还不太懂，真心抱歉。不过我问这个问题是因为我在看Python的手册和教程时（http://docs.python.org/2.7/tutorial），对循环是怎么工作的还是没完全搞明白。我写了一些简单的程序，觉得基础知识还可以，但不知怎么的，这个程序本来是用来列出所有小于或等于n的质数的，却没有正常运行：

n = int(raw_input("What number should I go up to? "))
p = 2
while p <= n:
        for i in range(2, p):
                if p%i == 0:
                        p=p+1 
        print "%s" % p,
        p=p+1
print "Done"

当我输入100时，输出是：

2 3 5 7 11 13 17 19 23 27 29 31 35 37 41 43 47 53 59 61 67 71 73 79 83 87 89 95 97 101 Done

看起来几乎是对的，但不知道为什么输出里却有27、35、95这些数字，它们其实是合数。我一直在试着分析我的循环是怎么工作的，但就是找不到它为什么突然跳过了可被整除的检查。我想如果有人能帮我看看，告诉我语法上哪里出了问题就好了。非常感谢！

Answer 1

这个方法应该可以用，而且稍微更优化了一些。

import math
for i in range(2, 99):
  is_prime = True
  for j in range(2, int(math.sqrt(i)+1)):
    if i % j == 0:
      is_prime = False
  if is_prime:
    print(i)

Answer 2

你的代码里有两个循环，一个在另一个里面。你可以试着把里面的循环换成一个函数，这样会更容易理解代码。然后确保这个函数是正确的，并且可以独立运行（和外面的循环分开）。

这是我对你原始代码的改写。这个改写运行得很好。

def is_prime(n):
    i = 2
    while i < n:
        if n%i == 0:
            return False
        i += 1
    return True


n = int(raw_input("What number should I go up to? "))

p = 2
while p <= n:
    if is_prime(p):
        print p,
    p=p+1

print "Done"

注意，is_prime() 这个函数没有碰到外面循环的索引。它是一个独立的纯函数。在里面的循环中增加 p 的值是个问题，而这个分解后的版本就没有这个问题。

现在我们可以轻松地用 for 循环来重写，我觉得代码会更好：

def is_prime(n):
    for i in range(2, n):
        if n%i == 0:
            return False
    return True


n = int(raw_input("What number should I go up to? "))

for p in range(2, n+1):
    if is_prime(p):
        print p,

print "Done"

在 Python 中，range() 函数不会包含你传入的上限值。所以在检查 < n 的内循环中，我们可以简单地用 range(2, n)，但在外循环中，因为我们想要 <= n，我们需要在 n 上加一，这样 n 才会被包含在内：range(2, n+1)

Python 有一些内置的功能，挺有趣的。你不需要马上学会所有这些技巧，但这里还有另一种写 is_prime() 的方法：

def is_prime(n):
    return not any(n%i == 0 for i in range(2, n))

这个方法和 for 循环版本的 is_prime() 一样工作。它把 i 设置为从 range(2, n) 中的值，并检查每一个。如果有任何测试失败，它就会停止检查并返回。如果它把 n 和范围内的每个数字都检查了一遍，并且没有任何一个数字能整除 n，那么这个数字就是质数。

再次强调，你不需要马上学会所有这些技巧，但我觉得当你学会的时候，它们会很有趣。

Answer 3

我会把这个程序重新组织成这样：

for p in range(2, n+1):
    for i in range(2, p):
        if p % i == 0:
            break
    else:
        print p,
print 'Done'

这样做可能更符合常见的写法（用for循环代替while循环），而且运行得很好。

外面的for循环会遍历从2到n的所有数字。

里面的循环则会遍历从2到p的所有数字。如果它找到一个能整除p的数字，就会跳出这个内部循环。

每当for循环没有被跳出时，else部分就会执行（打印出素数）。

然后程序在完成后会打印'Done'。

顺便提一下，你只需要遍历到p的平方根，因为每个因子都有一对。如果在平方根那里没有找到匹配的因子，那么在平方根之后就不会有其他因子了，这样这个数字就是素数。