| 最优的素数判断代码（Python）是这样写出来的 | 您所在的位置：网站首页 › 判断素数的代码是什么 › 最优的素数判断代码（Python）是这样写出来的 |
最优的素数判断代码（Python）是这样写出来的
|
素数判断是个很经典的问题，各种语言的程序设计课程都会涉及到，按照素数定义（除了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！ |
【本文地址】
公司简介
联系我们