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

...这种方法似乎可以，但我不确定是否正确，请有人确认一下吗？

- user1132011

---

我不理解这部分：prime % prime == 0？这不是模运算符吗？它每次都会返回0。 - keyser

如果这是作业，您应该标记它。 - Edwin Dalorzo

@Keyser 你的意思是每次都是 0 吗？ - jamylak

素数和素数总是返回0，这始终等于0。 - Marlin Pierce

质数 % 2 != 0吗？因此2和3不是质数。 - loki

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

如果你想要一个令人印象深刻的质数生成器，可以参考这里

- Fredrik Pihl

---

我觉得当 n = 1 时，这个失败了。 - Marcos

Answer 2

我不确定这是否是正确的方法

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

维基百科值得一读，了解各种（正确的）做法。

- NPE

Answer 3

素数的维基百科文章可以帮助您设计更好的算法。有许多算法，但基本算法并不那么复杂。

首先，我们需要明确一个质数必须是大于1的正整数。这个不变量意味着如果n小于2，你可以立即返回false。在你的代码中，n=0会失败。

一种朴素的方法是从1到n检查n的所有因子。如果你找到了两个因子，那么你就知道它是一个质数。

更直观的方法是得出每个数字都能被1和它本身整除的结论，因此，你只需要在2到n-1之间检查因子。当你找到n的一个因子时，你就可以得出n不是质数的结论。

改进的方法认识到所有偶数都能被2整除，因此，如果n不能被2整除，那么你只需要检查奇数因子。

最后，你不需要检查所有小于等于n的因子。只需要检查小于等于n的平方根的因子就足够了。如果你在达到这个阈值时没有找到因子，那么你可以得出n是一个质数的结论。

- Edwin Dalorzo