素数判断代码实现及其优化
共 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语句都可以实现循环结构功能,那么在本例中又该怎么做呢?
学生甲:循环结构必须包含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:
flag = True
i = 2
while i < n:
if n % i == 0:
flag = False
break
i += 1
return flag
教师:非常好!充分利用了break语句的特性,直接跳出循环,减少循环次数。还有别的方法吗?
改进方案二:
拓展思考3:
教师:设置标记变量flag来表示某种状态是常用的编程技巧,在上述程序中变量flag用来标记n是否为素数,最后返回flag的值。那么,变量flag是否是必需的呢?如果不定义flag,能否实现函数功能呢?
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
教师:太棒了!既简单明了,又清晰易懂!简直是返璞归真啊!
需要本文word文档、源代码和课后练习答案的,可以加入“Python算法之旅”知识星球参与讨论和下载文件,“Python算法之旅”知识星球汇集了数量众多的同好,更多有趣的话题在这里讨论,更多有用的资料在这里分享。
我们专注Python算法,感兴趣就一起来!
相关优秀文章: