质数检查函数有问题

Question

我写了一个函数，用来判断一个数字是不是质数，但无论怎么尝试，它似乎总是无法给出正确的结果。它还会打印出正在增加的n值。下面是这个函数的代码（顺便说一下，是用Python写的）：

def isPrime(x):
    for n in range(1, x):
        print n
        if x % n == 0:
            return False
    return True

如果我输入

isPrime(17)

这个函数返回

1
False

这里到底出了什么问题呢？

Answer 1

每个数字都能被1和它自己整除。质数是指只能被1和它自己整除的自然数。因此，如果你在循环中从1开始，每个数字 x 在第一次循环时都会满足条件 x % 1 == 0，这会返回 False。

要解决这个问题，你需要从2开始循环，而不是从1开始。另外，顺便提一下，你只需要循环到 sqrt(x)，因为如果存在一个数字 q > sqrt(x) 能整除 x，那么一定也会有一个数字 p = x / q 也能整除 x，而且 p < sqrt(x)。