python中的Primality测试

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

如果概率算法足够,请查看Miller-Rabin素性测试.你也可以证明一个数字是素数,例如Elliptic Curve Primality Proving(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 2

简而言之,您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语句.