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

Question

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

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, islice

def 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) # OverflowError
  
  from itertools import count, islice
  
  count(1)                        # Count from 1 to infinity with step=+1
  islice(count(1), 2147483648)    # Count from 1 to 2^31 with step=+1
  islice(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 11
  
  for 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 sqrt
from itertools import count, islice

def 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 math

def 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

Answer 4

如果a是素数,则while x:代码将永远运行,因为x将保留True.

那为什么while呢？

我想你想在找到一个因子时结束for循环,但不知道怎么做,所以你添加了因为它有一个条件.所以这是你如何做到的:

def is_prime(a):
    x = True 
    for i in range(2, a):
       if a%i == 0:
           x = False
           break # ends the for loop
       # no else block because it does nothing ...


    if x:
        print "prime"
    else:
        print "not prime"