检查数字是否是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 math import sqrt; from itertools import count, islicedef isPrime(n):
    return n > 1 and all(n%i for i in islice(count(2), int(sqrt(n)-1)))

这是一个非常简单和简洁的算法，因此它并不意味着接近最快或最优的素数检查算法。它的时间复杂度为O(sqrt(n))。头以上这里了解更多关于做正确的素性测试和他们的历史。

---

说明

我将给你一些关于将检查素数的几乎深奥的单行代码的内容：

• 首先，使用range()是一个坏主意，因为它会创建一个使用大量内存的数字列表。使用xrange()更好，因为它创建了一个生成器，它只需要记住你提供的初始参数，并在运行中生成每个数字。如果您使用的是Python 3或更高版本range()，则默认情况下已转换为生成器。顺便说一句，这根本不是最好的解决方案：尝试调用xrange(n)一些n这样的（这是C的最大值）。因此，创建范围生成器的最佳方法是使用：n > 231-1longOverflowErroritertools

  xrange(2147483647+1) # OverflowErrorfrom itertools import count, islice
  
  count(1)                        # Count from 1 to infinity with step=+1islice(count(1), 2147483648)    # Count from 1 to 2^31 with step=+1islice(count(1, 3), 2147483648) # Count from 1 to 3*2^31 with step=+3

• n如果你想检查是否n是素数，你实际上并不需要一直向前。你可以大大减少测试，只检查2到√(n)（平方根n）。这是一个例子：

  让我们找到所有除数n = 100，并将它们列在表中：

   2  x  50 = 100
   4  x  25 = 100
   5  x  20 = 100
  10  x  10 = 100 <-- sqrt(100)
  20  x  5  = 100     
  25  x  4  = 100
  50  x  2  = 100

  你很容易注意到，在平方根之后n，我们发现的所有除数实际上已经找到了。例如20已经发现了100/5。数字的平方根是我们发现的除数开始重复的确切中点。因此，要检查数字是否为素数，您只需要从2到2进行检查sqrt(n)。

• 为什么sqrt(n)-1呢，而不仅仅是sqrt(n)？那是因为提供给itertools.isliceobject 的第二个参数是要执行的迭代次数。迭代islice(count(a), b)后停止b。这就是为什么：

  for number in islice(count(10), 2):
      print number,# Will print: 10 11for number in islice(count(1, 3), 10):
      print number,# Will print: 1 4 7 10 13 16 19 22 25 28

• 该功能all(...)与以下内容相同：

  def all(iterable):
      for element in iterable:
          if not element:
              return False
      return True

  它确实检查了所有数字iterable，False当数字评估时返回False（这意味着只有数字为零）。那我们为什么要用呢？首先，我们不需要使用额外的索引变量（就像我们使用循环一样），除此之外：只是为了简洁，没有真正需要它，但它看起来不那么笨重单行代码而不是几行嵌套行。

扩大的视野

我要包含一个“解压缩”版本的isPrime()函数，以便更容易理解和阅读它：

from math import sqrtfrom itertools import count, islicedef isPrime(n):
    if n < 2:
        return False

    for number in islice(count(2), int(sqrt(n) - 1)):
        if n % number == 0:
            return False

    return True

Answer 2

有许多有效的方法可以测试primality（这不是其中之一），但你编写的循环可以用Python简洁地重写：

def is_prime(a):
    return all(a % i for i in xrange(2, a))

也就是说，如果a和2之间的所有数字（不包括在内）在分成a时给出非零余数，则a为素数。

Answer 3

如果您只有少量查询，这是查看数字是否为素数的最有效方法。如果你问很多数字，如果他们是主要的尝试Sieve of Eratosthenes。

import mathdef is_prime(n):
    if n == 2:
        return True
    if n % 2 == 0 or n <= 1:
        return False

    sqr = int(math.sqrt(n)) + 1

    for divisor in range(3, sqr, 2):
        if n % divisor == 0:
            return False
    return True