您当前的位置:首页 > 计算机 > 编程开发 > Python

最优的素数判断代码(Python)是这样写出来的

时间:09-09来源:作者:点击数:

素数判断是个很经典的问题,各种语言的程序设计课程都会涉及到,按照素数定义(除了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!

方便获取更多学习、工作、生活信息请关注本站微信公众号城东书院 微信服务号城东书院 微信订阅号
推荐内容
相关内容
栏目更新
栏目热门