在Python中检查数字是否是质数

2024-03-28 23:57:01 发布

您现在位置: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()

如果输入的数字不是质数,它会显示“非质数”,这是应该的,但如果数字是质数,它不会显示任何内容。你能帮我一下吗?


Tags: 代码truenumberinputifismaindef
3条回答

以下是我对这个问题的看法:

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))继续here学习更多关于正确完成的素性测试及其历史的知识。


解释

我会告诉你一些关于几乎深奥的一行代码的内幕,这些代码将检查素数:

  • 首先,使用range()确实是个坏主意,因为它将创建一个数字列表,这将使用大量内存。使用xrange()更好,因为它创建了一个生成器,它只需要记住您提供的初始参数,并动态生成每个数字。如果你在使用 Python 3或更高版本range()已默认转换为生成器。顺便说一句,这根本不是最好的解决方案:尝试为某些n调用xrange(n),这样n > 231-1(这是Clong的最大值)会提高OverflowError。因此,创建范围生成器的最佳方法是使用itertools

    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的平方根之后,我们找到的所有除数实际上都已经找到了。例如,在执行100/5操作时已找到20。一个数的平方根是我们发现的除数开始重复的确切中点。因此,要检查一个数是否是素数,只需要检查2到sqrt(n)

  • 那为什么是sqrt(n)-1,而不仅仅是sqrt(n)?这是因为提供给itertools.islice对象的第二个参数是要执行的迭代次数。islice(count(a), 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

如果只有几个查询,这是查看数字是否为素数的最有效方法。如果你问很多数字是否是素数,试试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

测试素性有很多有效的方法(这不是其中之一),但是您编写的循环可以用Python简洁地重写:

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

也就是说,如果2和a(不包括2和a)之间的所有数字在除以a时都给出非零余数,则a为素数

相关问题 更多 >