本文介绍了测试一个数字是否为质数的最快方法?的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
我正在尝试使用Python快速确定数字是否为素数。
我有两个函数来执行此操作。两者都返回True或False。
函数isPrime1返回FALSE非常快,因为它是一个不是质数的数字。例如,用一个大数字。但它在测试大素数的True时速度很慢。
函数isPrime2返回质数为True的速度更快。但是,如果一个数字很大并且不是质数,则返回值的时间太长。第一个函数与此配合使用效果更好。
我如何才能想出一个解决方案,该解决方案可能会对不是质数的大数快速返回False,并且对大数是质数会快速起作用?
def isPrime1(number): #Works well with big numbers that are not prime
state = True
if number <= 0:
state = False
return state
else:
for i in range(2,number):
if number % i == 0:
state = False
break
return state
def isPrime2(number): #Works well with big numbers that are prime
d = 2
while d*d <= number:
while (number % d) == 0:
number //= d
d += 1
if number > 1:
return True
else:
return False`
推荐答案
直到平方根大约是您能想到的最简单的除法。它最糟糕的情况是质数,因为所有除法都必须执行。无论如何,在十亿之前,几乎没有可测量的时间(1000000007
大约1.2毫秒)。
def Prime(n):
if n & 1 == 0:
return 2
d= 3
while d * d <= n:
if n % d == 0:
return d
d= d + 2
return 0
请注意,此版本返回最小除数或0
,而不是布尔值。
某些微优化是可能的(例如使用增量表),但我认为它们不会产生很大的收益。
有更复杂、更快的方法可用,但我不确定它们是否值得为这么小的n
而大惊小怪。
这篇关于测试一个数字是否为质数的最快方法?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!