我正在尝试一种快速的方法来确定一个数字是否是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 FirstPrimeFactor(n):
if n & 1 == 0:
return 2
d= 3
while d * d <= n:
if n % d == 0:
return d
d= d + 2
return n
请注意,此版本返回最小除数而不是布尔值。
一些微优化是可能的(例如使用增量表),但我认为它们不会产生很大的收益。
有更复杂和更快的方法可用,但我不确定它们是否值得为这么小的n
大惊小怪.
素数测试是一个非常棘手的话题。
在尝试加快代码速度之前,请尝试确保它按预期工作。我建议你从非常简单的算法开始,然后从那里开始构建。
有趣的是,isPrime2是有缺陷的。它为 6、10、12、... 返回 True
第3 行到第 6 行非常有说服力
while d*d <= number:
while (number % d) == 0:
number //= d
d += 1
当找到 number
d 的因子时,数字将更新为 number = number // d
,在 while 循环结束时,如果数字> 1,则返回True
使用 number = 6
完成代码:
isPrime2(6)
initialise> number := 6
initialise> d := 2
line3> check (2 * 2 < 6) :True
line4> check (6 % 2 == 0) :True
line5> update (number := 6//2) -> number = 3
line6> update (d : d + 1) -> d = 3
jump to line3
line3> check (3 * 3 < 3) :False -> GOTO line7
line7> check(number > 1) -> check(3 > 1) :True
line8> return True -> 6 is prime
这是我想到的
def is_prime(number):
# if number is equal to or less than 1, return False
if number <= 1:
return False
for x in range(2, number):
# if number is divisble by x, return False
if not number % x:
return False
return True