质数检查Python

Question

我写了一个非常简单的质数检查：

prime = int(input())
if prime % prime == 0 and prime % 2 != 0 and prime % 3 != 0 or prime == 2 or prime == 3:
    print("true")
else:
    print("false")

..。这似乎是有效的，但我不确定这是否是正确的方式，有人能确认一下吗？

Answer 1

我不确定这是不是正确的方式

不是。举一个反例，它认为25是一个质数。更糟糕的是，有无限多这样的反例。

Wikipedia值得阅读各种(正确的)方法来实现这一点。

Answer 2

简单到可以做到：

def isprime(n):
    """check if integer n is a prime"""
    # range starts with 2 and only needs to go up the squareroot of n
    for x in xrange(2, int(n**0.5)+1):
        if n % x == 0:
            return False
    return True

有关令人印象深刻的素数生成器，请参阅here

Answer 3

维基百科上关于primality的文章可以帮助你设计更好的算法。它们有很多，但基本的并不是那么复杂。

• 首先，脱离素数必须是大于1的正整数的事实。这个不变量意味着如果n<2，你可以立即返回false。在你的代码中，n=0失败了。
• 在一种简单的方法中，你可以检查n的从1到n的所有因子。如果你只找到两个，那么你就知道它是一个素数。
• 一个更直观的方法是得出结论，每个数字都可以被1和它自己整除，所以你可以只检查2和n-1之间的因子。当你找到n的一个因子时，你就可以得出n不是素数的结论。
• 一种改进的方法认识到所有偶数都可以被2整除，因此，如果n不能被2整除，那么从那里开始，你可以只检查奇数，你不需要检查直到n的所有因子。它应该足以检查n的平方根。如果当你达到这个阈值时，你还没有找到一个因子，那么你可以推断n是素数。