python - 质数检查 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

就这么简单：

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

有关令人印象深刻的素数生成器，请参见此处

Answer 2

我不确定它是否正确

它不是。举一个反例，它认为这25是一个素数。更糟糕的是，这样的反例数不胜数。

维基百科值得阅读各种（正确的）方法来做到这一点。

Answer 3

Wikipedia 关于素数的文章可以帮助您设计更好的算法。它们有很多，但基本的并不那么复杂。

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