素数判断是个很经典的问题,各种语言的程序设计课程都会涉及到,按照素数定义(除了1和自身,素数没有其他因数)很容易写出下面的代码:
def isPrime1(n):
for i in range(2, n):
if n%i == 0:
return False
return True
功能完全没有问题,就是非常非常非常非常慢。大家都明白,之所以那么慢是因为测试的范围实在是太大了,如何缩小范围呢,大家也是非常熟悉的:不需要测试从2到n-1这个完整的范围里有没有n的因数,只需要测试从2到n的平方根这个范围就可以了。假设m是n的平方根,如果2到m之间没有n的因数,那么m到n-1之间也必然没有n的因数。明白了道理之后,代码就好写了:
def isPrime2(n):
#与下面的截图稍微有一点点区别
m = int(n**0.5)+1
for i in range(2, m):
if n%i == 0:
return False
return True
可以想象,对于大整数来说,这样的改进是非常有意义的,具体能加速多少呢?看看下面的图就知道了:
太震撼了,速度确实提高很多,那么还能不能再进一步优化和提升呢?看下面的代码:
def isPrime3(n):
if n%2 == 0:
return False
#只判断奇数,范围缩小一半
for i in range(3, int(n**0.5)+1, 2):
if n%i == 0:
return False
return True
让我们再来比较一下速度:
perfect!