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

发布时间：2023-08-06 07:33:43 来源：程序员客栈

说在前面

【资料图】

素数判断是经典数论问题，也是算法教学中的经典案例，利用素数定义判断正整数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

教师：非常棒！此处虽然没有设置标记变量，但是利用了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算法，感兴趣就一起来！