素数检查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是一个素数.更糟糕的是,存在无数许多这样的反例.

维基百科值得阅读各种(正确的)方法.