我写了下面的代码,它应该检查输入的数字是否是质数,但有一个问题我无法解决:
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()
如果输入的数字不是质数,它会显示“非质数”,这是应该的,但如果数字是质数,它不会显示任何内容。你能帮我一下吗?
以下是我对这个问题的看法:
这是一个非常简单和简洁的算法,因此它并不意味着任何接近最快或最优化的素性检查算法。它的时间复杂度为
O(sqrt(n))
。继续here学习更多关于正确完成的素性测试及其历史的知识。解释
我会告诉你一些关于几乎深奥的一行代码的内幕,这些代码将检查素数:
首先,使用
range()
确实是个坏主意,因为它将创建一个数字列表,这将使用大量内存。使用xrange()
更好,因为它创建了一个生成器,它只需要记住您提供的初始参数,并动态生成每个数字。如果你在使用 Python 3或更高版本range()
已默认转换为生成器。顺便说一句,这根本不是最好的解决方案:尝试为某些n
调用xrange(n)
,这样n > 231-1
(这是Clong
的最大值)会提高OverflowError
。因此,创建范围生成器的最佳方法是使用itertools
:如果要检查
n
是否是质数,实际上不需要一直到n
为止。您可以显著地减少测试,并且只检查从2到√(n)
(平方根n
)。下面是一个例子:让我们找出
n = 100
的所有除数,并将它们列在表中:你很容易就会注意到,在
n
的平方根之后,我们找到的所有除数实际上都已经找到了。例如,在执行100/5
操作时已找到20
。一个数的平方根是我们发现的除数开始重复的确切中点。因此,要检查一个数是否是素数,只需要检查2到sqrt(n)
。那为什么是
sqrt(n)-1
,而不仅仅是sqrt(n)
?这是因为提供给itertools.islice
对象的第二个参数是要执行的迭代次数。islice(count(a), b)
在迭代后停止。这就是为什么:函数
all(...)
与以下相同:它逐字地检查
iterable
中的所有数字,当一个数字的计算结果为False
时返回False
(这意味着仅当数字为零时)。那我们为什么要用它呢?首先,我们不需要使用额外的索引变量(就像我们使用循环一样),除此之外:为了简洁起见,实际上并不需要它,但是只使用一行代码而不是多行嵌套代码看起来就不那么庞大了。扩展版本
我包括一个
isPrime()
函数的“解包”版本,以便更容易理解和阅读:如果只有几个查询,这是查看数字是否为素数的最有效方法。如果你问很多数字是否是素数,试试Sieve of Eratosthenes。
测试素性有很多有效的方法(这不是其中之一),但是您编写的循环可以用Python简洁地重写:
也就是说,如果2和a(不包括2和a)之间的所有数字在除以a时都给出非零余数,则a为素数
相关问题 更多 >
编程相关推荐