素数检查函数存在问题。

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

这里出了什么问题？

- Do A Barrel Roll

---

素数的定义是错误的。 - yosukesabai

只是一个提示：有很多优化质数检查器的方法，但一个简单的方法是：只需检查平方根x以内的数字。因此，添加 from math import sqrt, floor，然后将您的范围更改为 range(2,floor(sqrt(x)))。 - Ord

你的原始逻辑，作为Pythonic的一行代码：def isPrime(x): return x > 1 and all(x % n for n in xrange(2,x)) - wim

为什么数字1不被认为是质数？ - jfs

Answer 1

每个数字都能被1和自己整除。质数是一种自然数，它没有其他正约数，除了1和它本身。因此，如果你用1开始for循环，每个数字x都会在第一次迭代中满足条件x % 1 == 0，返回False。

为了解决这个问题，你需要从2开始循环。另外，顺便说一下，你只需要循环从2到sqrt(x)，因为如果存在一个大于sqrt(x)的数q可以整除x，那么也必须存在一个数p = x / q也可以整除x，且p < sqrt(x)。

- João Silva