素数判断代码实现及其优化

Python算法之旅

共 4110字,需浏览 9分钟

 ·

2023-08-07 17:44

说在前面

素数判断是经典数论问题,也是算法教学中的经典案例,利用素数定义判断正整数n是否为素数,是解决复杂素数问题的基础,该问题涉及循环结构和枚举算法,其代码实现形式多样,可作为入门级算法学习的经典例题,值得深入研究。

原型展示:

自定义函数is_prime(n)的功能是判断正整数n是否为素数,若为素数返回True,否则返回False。请将缺失的代码补充完整。

def is_prime(n):

    flag = True

    for i in range(2, n):

        if 填空1:

            flag = False

    填空2

题目解析:

根据素数的定义可知,素数不能被1和它本身外的自然数整除,若n能被i整除,说明n不是素数。故第1空答案为n % i == 0

变量flag用来标记n是否为素数,先假设n为素数,为flag取初值True。若n不是素数,则设置flag=False。函数返回flag的值表示判断结果,故第2空答案为return flag

拓展思考1:

教师:函数is_prime()使用for循环来遍历n所有可能的因数,以判断其是否为素数。我们知道for语句和while语句都可以实现循环结构功能,那么在本例中又该怎么做呢?

请同学们在函数is_prime()的基础上,用while循环语句代替for循环语句,编写代码实现相同功能。

学生甲:循环结构必须包含3个环节:为循环变量i设置初值、判断循环结束条件和更新循环变量的值。for循环语句比较简明,它把这3个环节都浓缩在一条语句中了,而while循环需要使用3条语句才能实现这3个功能。参考代码如下:

def is_prime2(n):

    flag = True

    i = 2

    while i < n:

        if n % i == 0:

            flag = False

        i += 1

    return flag

拓展思考2:

教师:函数is_prime()和is_prime2()都能够实现程序功能,但是效率太低,请同学们思考可以从哪些方面来改进算法,提高程序效率?
改进方案一:
学生甲:当找到n的第一个因数以后,就可以确定n为合数,没必要再枚举其他因数了。所以应该在语句flag=False后面添加语句break,直接跳出循环,可以提高程序效率。参考代码如下:
def is_prime3(n):
    flag = True
    for i in range(2, n):
        if n % i == 0:
            flag = False
            break
    return flag
def is_prime4(n):

    flag = True

    i = 2

    while i < n:

        if n % i == 0:

            flag = False

            break

        i += 1

    return flag

教师:非常好!充分利用了break语句的特性,直接跳出循环,减少循环次数。还有别的方法吗?

改进方案二:

学生乙:因为n不存在大于n//2的因数,故可以把i的最大值从n-1缩小到n//2,这样就缩小了枚举范围。参考代码如下:
def is_prime5(n): #同理可以对is_prime4()进行改进
    flag = True
    for i in range(2, n//2+1):
        if n % i == 0:
            flag = False
            break
    return flag
学生丙:根据因数成对出现的特性,我们还可以进一步缩小枚举范围,把i的上限设置为n的平方根。参考代码如下:
def is_prime6(n): #同理可以对is_prime4()进行改进
    flag = True
    for i in range(2, int(n**0.5)+1):
        if n % i == 0:
            flag = False
            break
    return flag

拓展思考3:

教师:设置标记变量flag来表示某种状态是常用的编程技巧,在上述程序中变量flag用来标记n是否为素数,最后返回flag的值。那么,变量flag是否是必需的呢?如果不定义flag,能否实现函数功能呢?

自定义函数is_prime7(n)的功能是判断正整数n是否为素数,若为素数返回True,否则返回False。请将缺失的代码补充完整。

def is_prime7(n):

    i = 2

    while i < n:

        if n % i == 0:

            break

        i += 1

    填空1

学生丁:根据代码可知,若n为素数,则程序没有机会执行break语句,while循环结束后,有i==n;否则执行break语句,中途跳出while循环,循环结束后仍然满足i<n。故填空1的答案为return i == n

教师:非常棒!此处虽然没有设置标记变量,但是利用了while循环的特性,根据循环结束后循环条件是否依然成立来判断程序是否执行了break语句,构思非常巧妙。

改进方案三:

学生甲:老师,我还有更好的方法!

教师:是吗?说来听听。

学生甲:函数is_prime7()虽然构思巧妙,但是不过直白,需要转一道弯才能理解。考虑到这是一个自定义函数,我们可以在找到n的第一个因数后直接返回False;只有当n不存在因数时,才返回True。这样代码更简明,参考代码如下:

def is_prime8(n):

    for i in range(2, int(n**0.5)+1):

        if n % i == 0:

            return False

    return True

教师:太棒了!既简单明了,又清晰易懂!简直是返璞归真啊!

最后送给大家一道课后思考题:如何使用while循环语句来代替函数is_prime8()中的for循环语句呢?


需要本文word文档、源代码和课后练习答案的,可以加入“Python算法之旅”知识星球参与讨论和下载文件,Python算法之旅”知识星球汇集了数量众多的同好,更多有趣的话题在这里讨论,更多有用的资料在这里分享。

我们专注Python算法,感兴趣就一起来!

相关优秀文章:

阅读代码和写更好的代码

最有效的学习方式

Python算法之旅文章分类

浏览 434
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报