素数检查功能有问题

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开始for循环,则每个数字x都将x % 1 == 0在第一次迭代中传递条件,然后返回False.

为了解决这个问题,你需要开始与2,而不是1.另外你的循环,作为一个侧面说明,你只需要循环2至sqrt(x),因为如果存在数q > sqrt(x)划分x,那么也必须是一个数字p = x / q,其也划分x,和p < sqrt(x).