python中的素性测试

Question

我试图用Python做一个简单的素性测试。

根据维基百科，aprimality test如下：

Given an input number n, check whether any integer m from 2 to n − 1 divides n. If n is divisible by any m then n is composite, otherwise it is prime.

我一开始就排除了偶数（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 primality test概率算法是否足够。你也可以证明一个数是素数，例如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

函数实际上返回您的数字是否为奇数。

实际上，你要做的是检查2是否除以你的数字，然后立即返回。你从来不查其他号码。

您需要做的是将这个返回值从if's else子句中取出，并将for循环返回到主函数体中。

顺便说一句，如果你在寻找低于给定数字的素数，你可以把你找到的素数存储在内存中，然后试着用这些素数除以你的新数字！ （因为如果d是复合的，除以q，那么p的存在使得p是质数，p除以q）。

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语句的一部分。