素数判断代码实现及其优化
说在前面
素数判断是经典数论问题，也是算法教学中的经典案例，利用素数定义判断正整数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算法，感兴趣就一起来！
相关优秀文章：