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。

- Mahmoud Hanafy

---

请注意，您无需检查到 n-1。只需要检查到 sqrt(n) 就足够了，因为任何大于此值的数肯定不能被整除，或者已经被小于其平方根的数字检查过了。 - Paul Manta

还要注意，所有提到的候选生成方法都会进行不必要的复制。xs = range(1, x, 2); xs[0] = 2 不会进行复制，并且使用 xrange（在3.x中是普通的 range）和 itertools.chain，甚至可以避免同时存储多个候选项。 - user395760

@PaulManta range 不接受浮点数，而 sqrt(n) 返回的是浮点数，强制转换为整数会因四舍五入误差而导致结果出错。 - Mahmoud Hanafy

@MahmoudHossam：啊，我真傻。我刚才读错了(0, 2)。 - Marcelo Cantos

相关：Python是否存在用于素数相关函数的库？ - maxschlepzig

Answer 1

如果概率算法足够的话，可以查看Miller-Rabin素性检验算法。您还可以使用例如椭圆曲线素性证明（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

我已经将a ** 0.5替换为sqrt(a)，以使事情更加清晰。使用平方根是为了不查看比必要的因子更多的因子。

- Morten Kristensen

---

问题要求我使用试除法。 - Mahmoud Hanafy

这是一道作业。这个练习是教授编程的手段！ - David Heffernan

@David：啊，我懂了，我的错。尽管引用可能有点多，但我仍然喜欢Morten的算法。它很简洁，一开始学习很难，但是发展这种技能非常棒。他还返回评估而不是单独的T/F语句，这也很好理解。他暗示“试除法”并不是真正高效的方法。 - Mike Williamson

@MikeWilliamson 这里的简洁性非常糟糕。更好的方法是使用更多行并添加一些解释性变量。过度简洁是许多程序员的可怕缺陷。如果这个代码被适当地分散在4或5行上，它将会更快速阅读。更容易阅读。更容易检查。对于像提问者这样的初学者来说，这个答案中的代码就像黑魔法一样。 - David Heffernan

我喜欢使用any语句代替all的想法。这将把一个完整的列表推导式转换为搜索。但是，我不确定一旦找到第一个除数x，操作是否会中断并返回False，因为range一次返回所有值。这个问题已经解决了吗？还是应该使用xrange？ - Sik

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语句。

- alf

---

虽然这个解决方案完全没问题，但是以下带有“while”循环的解决方案会明显更快。但在我看来，这并不是最优解决方案。 - Mike Williamson

考虑到这是一份作业，我并没有假设性能很重要。问题本身是“有什么问题”，而不是如何改进它。 - alf

抱歉...我并不是想批评你的解决方案。你是正确的。我只是想知道为什么社区会投票支持这个解决方案，而不是那个只到sqrt(n)的解决方案。 - Mike Williamson

将第二个return放在else块中是否有任何原因？由于循环中没有break语句，因此for/else结构相当不常见且在此处不必要。 - Clément

那是两年前的事了。我猜原因是为了将变化降至最低。 - alf

Answer 3

问题在于你将 return False 放在了 else 子句中，而不是函数的结尾。因此，在检查第一个因子后，你的函数将立即返回，而不会继续检查其他因子。

这里是一个类似于你的简单素性测试：

def is_prime(n):
    d = 2
    while d * d <= n:
        if n % d == 0:
            return False
        d += 1
    return n > 1

- Daniel Lubarov

---

（我没有给你的帖子点踩，但是...）计算一次平方根肯定比计算n次平方更便宜。而且，while循环不太符合Pythonic风格；使用range()。 - Marcelo Cantos

我同意range更具有Python风格，但另一方面，整数乘法很便宜，而sqrt方法需要四舍五入，这在我看来似乎不太优雅。 - Daniel Lubarov

平方根上面的下一个整数不能被n整除。因此，向下取整是安全的，这只需要将其转换为int即可。此外，我会在一周中的任何一天都更喜欢O(sqrt(N))而不是O(N)，尽管有些不太优雅（当然，在合理范围内）。 - Marcelo Cantos

你是对的，转换为整数类型可以很好地运作。但是这段代码也是O(sqrt(n))，而且可能至少和列表查找（对于Python 2）或迭代器（对于3）的开销一样快。 - Daniel Lubarov

我今晚大脑有点半开半关。 - Marcelo Cantos

Answer 4

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

事实上，你正在检查2是否能整除你的数字，并立即返回。你从未检查其他数字。

你需要将这个在if结构中返回true的语句移出else子句，并将for循环放回主函数体中。

顺便说一下，如果你正在寻找比给定数字更小的质数，你可以将你发现的质数存储在内存中，然后只尝试用这些质数来除以新的数字！（因为如果d是合成数并且除q外，那么p存在是质数且可以被q整除）。

- Thomas Orozco