Python中的素数测试

Question

我正在尝试在Python中做一个简单的质数测试。

根据维基百科，质数测试的定义是这样的：

给定一个输入数字n，检查从2到n-1之间的任何整数m是否能整除n。如果n能被任何m整除，那么n就是合数，否则它就是质数。

我首先排除了偶数（除了2）作为质数的候选者。

def prime_candidates(x):
    odd = range(1, x, 2)
    odd.insert(0, 2)
    odd.remove(1)
    return odd

然后我写了一个函数来根据上面的规则检查质数。

def isprime(x):
    for i in range(2, x-1):
            if x % i == 0:
                    return False
            else:
                    return True

这是主要的函数，它会遍历一个包含8000个质数候选者的列表，并测试它们是否是质数。

def main():
    end = 8000
    candidates = prime_candidates(end)
    for i in candidates:
            if isprime(i) and i < end:
                    print 'prime found ' + str(i)

问题是，isprime函数对一些不是质数的数字返回了True。

Answer 1

你的函数实际上是在判断一个数字是不是奇数。

你做的事情是检查这个数字能不能被2整除，如果能就立刻返回结果。你并没有检查其他的数字。

你需要把这个返回“真”的部分从条件语句的“否则”里拿出来，放回到主函数的主体部分。

顺便说一下，如果你想找出小于某个数字的质数，你可以把找到的质数存起来，然后只用这些质数去尝试除你的新数字！因为如果d是合数并且能整除q，那么一定存在一个质数p，它也能整除q。

Answer 2

如果你需要一个概率性的算法来判断一个数是否是质数，可以看看米勒-拉宾质数测试。当然，你也可以用椭圆曲线质数证明（ECPP）来证明一个数是质数，但这样做会更复杂一些。

一个简单的试除法算法如下：

def prime(a):
     return not (a < 2 or any(a % x == 0 for x in range(2, int(a ** 0.5) + 1)))

编辑：这是一个更易于理解的版本，因为第一个解决方案比较简洁，可能不太好读：

from math import sqrt
def prime(a):
    if a < 2: return False
    for x in range(2, int(sqrt(a)) + 1):
        if a % x == 0:
            return False
    return True

我把 sqrt(a) 替换成了 a ** 0.5，这样更清楚。使用平方根是为了避免检查不必要的因子。

Answer 3

简单来说，你的 isprime(x) 函数是用来检查一个数字是否是质数的，它会先判断这个数字是否是奇数，如果是偶数的话就直接退出，特别是在 if x % 2 == 0 这一行。

试着做个小改动，这样你就能真正进行循环了：

def isprime(x):
    for i in range(2, x-1):
        if x % i == 0:
            return False
    else:
        return True

注意，现在 else: 是和 for 循环在一起，而不是和 if 语句在一起。