素数求解及其优化策略
本帖最后由 codeshealth 于 2023-11-2 19:34 编辑素数问题
素数判断是数论中的一个经典问题，同时也是算法教学中的一个经典案例。素数的定义是：如果一个正整数n只能被1和它本身整除，那么它就是一个素数。判断一个正整数是否为素数，是解决更复杂的素数问题的基石。在这个问题中，我们通常会涉及到循环结构和枚举算法。其代码实现形式多种多样，因此，它被广泛用作入门级算法学习的经典例题。对于想要深入学习算法的人来说，这是一个非常值得研究的问题。
问题描述：
自定义函数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，这样就缩小了枚举范围。参考代码如下.
学生丙：根据因数成对出现的特性，我们还可以进一步缩小枚举范围，把i的上限设置为n的平方根。参考代码如下：
def is_prime5(n):
flag = True
for i in range(2, n//2+1):
if n % i == 0:
flag = False
break
return flag
def is_prime6(n):
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循环语句呢？
改进方案四：
素数筛选法:
老师：你好，同学们。今天我们要学习一种求素数的方法，叫做素数筛法。首先，让我们了解一下什么是素数。素数是一个大于1的自然数，除了1和它本身外，不能被其他自然数整除的数。例如，2、3、5、7等都是素数。
学生：老师，我不明白什么是素数筛法。
老师：没关系，让我们一步步来理解。首先，我们要理解素数筛法的原理。素数筛法的原理是根据一个数的因子的特性，将这个数划分为若干个小组，然后对每个小组进行筛选，找出其中的素数。
学生：老师，我还是不太明白。
老师：好的，让我们通过一个例子来理解。假设我们要找100以内的所有素数。我们可以将100以内的所有自然数划分为若干个小组。例如，我们可以将它们按照奇偶性分成两组，然后分别对每组进行筛选。
学生：老师，我还是有点糊涂。
老师：好的，让我们通过代码来学习。这是使用素数筛法求100以内所有素数的Python代码：
def prime_sieve(n):
primes = []
for i in range(2, n+1):
if i % 2 == 0:
continue
for j in range(i, n+1, i):
if j % i == 0:
break
else:
primes.append(i)
return primes
学生：老师，我看不懂这段代码。
老师：没关系，让我们一步步来分析。首先，我们定义一个空列表primes来存储所有的素数。然后，我们从2开始遍历到n，对于每个数i，我们先检查它是否是偶数，如果是，就跳过它。这是因为偶数除了2以外都不是素数。
学生：老师，我明白了。但是接下来的代码我还是看不懂。
老师：没关系，让我们继续分析。接下来，我们用一个循环来检查每个数i是否是合数。具体来说，我们从i开始，以i为步长遍历到n。对于每个数j，我们检查它是否能被i整除，如果能，就跳出循环。否则，我们将i添加到primes列表中。
学生：老师，我明白了。这段代码的意思是，我们先跳过偶数，然后用一个循环来检查每个数是否是合数。如果一个数不能被其他数整除，那么它就是一个素数。
老师：非常好！你理解得很正确。这就是素数筛法的原理。通过这个代码，我们可以求出100以内的所有素数。你可以试着运行一下这个代码，看看结果是什么。
学生：老师，我运行了这个代码，但是结果不对。
老师：好的，让我们检查一下。可能的原因可能是我们在检查一个数是否是合数时，没有正确地跳出循环。让我们来修复这个问题。
修复后的代码如下：
def prime_sieve(n):
primes = []
for i in range(2, n+1):
if i % 2 == 0:
continue
for j in range(i, n+1, i):
if j % i == 0:
break
else:
primes.append(i)
return primes
学生：老师，这次的代码结果还是不对。
老师：好的，让我们再检查一下。可能的原因是我们的步长设置错误，导致循环中的j并不是以i为间隔。正确的步长应该是i的平方。让我们来修复这个问题。
修复后的代码如下：
def prime_sieve(n):
primes = []
for i in range(2, n+1):
if i % 2 == 0:
continue
for j in range(i, n+1, i**2):
if j % i == 0:
break
else:
primes.append(i)
return primes
学生：老师，这次的代码结果还是不对。
老师：好的，让我们再检查一下。可能的原因是我们的筛选条件设置错误，导致将一些合数误认为是素数。正确的筛选条件应该是如果j不能被i的任何因数整除，才将i添加到primes列表中。让我们来修复这个问题。
修复后的代码如下：
def prime_sieve(n):
primes = []
for i in range(2, n+1):
if i % 2 == 0:
continue
for j in range(i, n+1, i):
if j % i == 0:
break
else:
primes.append(i)
return primes
学生：老师，这次的代码结果还是不对。
老师：好的，让我们再检查一下。可能的原因是我们的筛选条件设置错误，导致将一些合数误认为是素数。让我们来修复这个问题。
修复后的代码如下：
def prime_sieve(n):
primes = * (n+1)
primes = primes = False
for i in range(2, int(n**0.5)+1):
if primes:
for j in range(i*i, n+1, i):
primes = False
return ]
学生：老师，这次的结果是正确的。但是我还是有点不明白这个算法的原理。
老师：好的，让我们来详细讲解一下这个算法的原理。首先，我们将从2到n的所有数字标记为素数。然后，我们从2开始，将它的倍数都标记为合数。这样，我们就可以将所有的合数筛选出来，剩下的就是素数。这个算法的效率非常高，因为我们将范围缩小到了原来的1/3左右。
学生：老师，我明白了。这个算法真的很巧妙。谢谢您的讲解！
老师：不客气，希望这个算法能帮助你更好地理解素数的概念和求解方法。如果你还有其他问题，随时都可以问我。
页:
[1]