检查数字是否是Python中的素数

Question

检查数字是否是Python中的素数

我写了下面的代码，应该检查输入的数字是否是素数，但是有一个问题我无法通过：

def main():n = input("Please enter a number:")is_prime(n)def is_prime(a):
    x = True 
    for i in (2, a):
            while x:
               if a%i == 0:
                   x = False
               else:
                   x = True


    if x:
        print "prime"
    else:
        print "not prime"main()

如果输入的数字不是素数，则显示“非素数”，因为它应该是，但如果数字是素数，则它不显示任何内容。你能帮帮我吗？

Answer 1

以下是我对这个问题的看法：from&nbsp;math&nbsp;import&nbsp;sqrt;&nbsp;from&nbsp;itertools&nbsp;import&nbsp;count,&nbsp;islicedef&nbsp;isPrime(n): &nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;n&nbsp;>&nbsp;1&nbsp;and&nbsp;all(n%i&nbsp;for&nbsp;i&nbsp;in&nbsp;islice(count(2),&nbsp;int(sqrt(n)-1)))这是一个非常简单和简洁的算法，因此它并不意味着接近最快或最优的素数检查算法。它的时间复杂度为O(sqrt(n))。头以上这里了解更多关于做正确的素性测试和他们的历史。说明我将给你一些关于将检查素数的几乎深奥的单行代码的内容：首先，使用range()是一个坏主意，因为它会创建一个使用大量内存的数字列表。使用xrange()更好，因为它创建了一个生成器，它只需要记住你提供的初始参数，并在运行中生成每个数字。如果您使用的是Python 3或更高版本range()，则默认情况下已转换为生成器。顺便说一句，这根本不是最好的解决方案：尝试调用xrange(n)一些n这样的（这是C的最大值）。因此，创建范围生成器的最佳方法是使用：n > 231-1longOverflowErroritertoolsxrange(2147483647+1)&nbsp;#&nbsp;OverflowErrorfrom&nbsp;itertools&nbsp;import&nbsp;count,&nbsp;islice count(1)&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;#&nbsp;Count&nbsp;from&nbsp;1&nbsp;to&nbsp;infinity&nbsp;with&nbsp;step=+1islice(count(1),&nbsp;2147483648)&nbsp;&nbsp;&nbsp;&nbsp;#&nbsp;Count&nbsp;from&nbsp;1&nbsp;to&nbsp;2^31&nbsp;with&nbsp;step=+1islice(count(1,&nbsp;3),&nbsp;2147483648)&nbsp;#&nbsp;Count&nbsp;from&nbsp;1&nbsp;to&nbsp;3*2^31&nbsp;with&nbsp;step=+3n如果你想检查是否n是素数，你实际上并不需要一直向前。你可以大大减少测试，只检查2到√(n)（平方根n）。这是一个例子：让我们找到所有除数n = 100，并将它们列在表中：&nbsp;2&nbsp;&nbsp;x&nbsp;&nbsp;50&nbsp;=&nbsp;100 &nbsp;4&nbsp;&nbsp;x&nbsp;&nbsp;25&nbsp;=&nbsp;100 &nbsp;5&nbsp;&nbsp;x&nbsp;&nbsp;20&nbsp;=&nbsp;100 10&nbsp;&nbsp;x&nbsp;&nbsp;10&nbsp;=&nbsp;100&nbsp;<--&nbsp;sqrt(100) 20&nbsp;&nbsp;x&nbsp;&nbsp;5&nbsp;&nbsp;=&nbsp;100&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 25&nbsp;&nbsp;x&nbsp;&nbsp;4&nbsp;&nbsp;=&nbsp;100 50&nbsp;&nbsp;x&nbsp;&nbsp;2&nbsp;&nbsp;=&nbsp;100你很容易注意到，在平方根之后n，我们发现的所有除数实际上已经找到了。例如20已经发现了100/5。数字的平方根是我们发现的除数开始重复的确切中点。因此，要检查数字是否为素数，您只需要从2到2进行检查sqrt(n)。为什么sqrt(n)-1呢，而不仅仅是sqrt(n)？那是因为提供给itertools.isliceobject&nbsp;的第二个参数是要执行的迭代次数。迭代islice(count(a), b)后停止b。这就是为什么：for&nbsp;number&nbsp;in&nbsp;islice(count(10),&nbsp;2): &nbsp;&nbsp;&nbsp;&nbsp;print&nbsp;number,#&nbsp;Will&nbsp;print:&nbsp;10&nbsp;11for&nbsp;number&nbsp;in&nbsp;islice(count(1,&nbsp;3),&nbsp;10): &nbsp;&nbsp;&nbsp;&nbsp;print&nbsp;number,#&nbsp;Will&nbsp;print:&nbsp;1&nbsp;4&nbsp;7&nbsp;10&nbsp;13&nbsp;16&nbsp;19&nbsp;22&nbsp;25&nbsp;28该功能all(...)与以下内容相同：def&nbsp;all(iterable): &nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;element&nbsp;in&nbsp;iterable: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;not&nbsp;element: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;False &nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;True它确实检查了所有数字iterable，False当数字评估时返回False（这意味着只有数字为零）。那我们为什么要用呢？首先，我们不需要使用额外的索引变量（就像我们使用循环一样），除此之外：只是为了简洁，没有真正需要它，但它看起来不那么笨重单行代码而不是几行嵌套行。扩大的视野我要包含一个“解压缩”版本的isPrime()函数，以便更容易理解和阅读它：from&nbsp;math&nbsp;import&nbsp;sqrtfrom&nbsp;itertools&nbsp;import&nbsp;count,&nbsp;islicedef&nbsp;isPrime(n): &nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;n&nbsp;<&nbsp;2: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;False &nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;number&nbsp;in&nbsp;islice(count(2),&nbsp;int(sqrt(n)&nbsp;-&nbsp;1)): &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;n&nbsp;%&nbsp;number&nbsp;==&nbsp;0: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;False &nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;True

Answer 2

有许多有效的方法可以测试primality（这不是其中之一），但你编写的循环可以用Python简洁地重写：def&nbsp;is_prime(a): &nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;all(a&nbsp;%&nbsp;i&nbsp;for&nbsp;i&nbsp;in&nbsp;xrange(2,&nbsp;a))也就是说，如果a和2之间的所有数字（不包括在内）在分成a时给出非零余数，则a为素数。

Answer 3

如果您只有少量查询，这是查看数字是否为素数的最有效方法。如果你问很多数字，如果他们是主要的尝试Sieve of Eratosthenes。import&nbsp;mathdef&nbsp;is_prime(n): &nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;n&nbsp;==&nbsp;2: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;True &nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;n&nbsp;%&nbsp;2&nbsp;==&nbsp;0&nbsp;or&nbsp;n&nbsp;<=&nbsp;1: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;False &nbsp;&nbsp;&nbsp;&nbsp;sqr&nbsp;=&nbsp;int(math.sqrt(n))&nbsp;+&nbsp;1 &nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;divisor&nbsp;in&nbsp;range(3,&nbsp;sqr,&nbsp;2): &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;n&nbsp;%&nbsp;divisor&nbsp;==&nbsp;0: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;False &nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;True