问题描述
我正在尝试一种快速的方法来确定使用Python是否为质数.
I'm trying to get a fast way to determine if a number is prime using Python.
我有两个功能可以做到这一点.两者都返回True或False.
I have two functions to do this. Both return either True or False.
函数isPrime1返回的速度非常快False是数字不是素数.例如,数量很大.但是对于大质数测试True的速度很慢.
Function isPrime1 is very fast to return False is a number is not a prime. For example with a big number. But it is slow in testing True for big prime numbers.
函数isPrime2更快地返回质数的True.但是,如果一个数字很大而又不是素数,则返回值花费的时间太长.第一个功能可以更好地工作.
Function isPrime2 is faster in returning True for prime numbers. But if a number is big and it is not prime, it takes too long to return a value. First function works better with that.
我如何提出一个解决方案,对于一个不是素数的大数,可以快速返回False,而对于一个素数的大数,可以快速地工作呢?
How can I come up with a solution that could quickly return False for a big number that is not prime and would work fast with a big number that is prime?
`
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毫秒).
Exhaustive division until the square root is about the simplest you can think of. Its worst case is for primes, as all divisions must be performed. Anyway, until a billion, there is virtually no measurable time (about 1.2 ms for 1000000007
).
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
而不是布尔值.
Note that this version returns the smallest divisor or 0
rather than a boolean.
可以进行一些微优化(例如使用增量表),但是我认为它们不会带来很大的收益.
Some micro-optimizations are possible (such as using a table of increments), but I don' think they can yield large gains.
有很多更先进,更快速的方法可用,但我不确定它们是否值得这么小的 n
大惊小怪.
There are much more sophisticated and faster methods available, but I am not sure they are worth the fuss for such small n
.
这篇关于测试数字是否为素数的最快方法的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!