Python赋能数学学习7:质数判断算法演进,实际效率对比分析
- 2026-10-11 07:14:28
一、什么是质数，如何判断是否是质数？
质数是指大于 1，并且只能被 1 和它本身整除的正整数。
例如：
2、3、5、7、11 都是质数 4 可以被 2 整除，所以 4 不是质数 9 可以被 3 整除，所以 9 不是质数
判断一个数n是不是质数，最简单的方法是从 2 开始，逐个尝试除数，直到 。如果 能被任何一个除数整除，那么 就不是质数。但这样的算法效率非常低，尤其是当 很大时。
如何通过数学知识来逐步优化质数判断算法，减少不必要的尝试，从而提高效率呢？这是我们这次研究的核心问题。
二、四种算法背后的数学原理
1. 算法一：检查 2 到 (暴力算法)
如果 能被 2 到 之间的任何一个整数整除，那么 就不是质数。反之，如果这些数都不能整除 ，那么 是质数。
这是最简单的暴力算法，但效率非常低。对于一个质数 ，需要检查 个除数。
对于质数 ，最极端的情况下要检查 2、3、4、...、，总共 次判断。
2. 算法二：检查 2 到
假设 是一个合数，他的最小真因子肯定大于等于2，则他的真因子肯定小于等于 。因此，如果 能被任何一个小于等于 的整数整除，那么 就不是质数。
这样我们可以在暴力破解的基础上减少一半的判断次数。对于质数 ，最极端的情况下要检查 2、3、4、...、，总共 次判断。
比如100的话，我们只需要检查2、3、4、...、50就可以了。
3. 算法三：检查 2 到
如果 是合数，那么一定可以写成：
他们是成队出现的，我们对成队的因数进行按照大小进行分组分析：
举例：一个数 的因数成对出现，
例如：
100 的因数对是 (1, 100)、(2, 50)、(4, 25)、(5, 20)、(10, 10)
100的因数对中，小的因数分别是 1、2、4、5、10，而且100的因数对中的小因数肯定不会大于 。
★因为，如果 是合数，如果他的因数对中小的因数大于 ，那么大的因数也大于 ，那两个数的乘积肯定大于 。
比如100的因数对中不会存在(11,?),(12,?)这样的因数对，因为11和12都大于10了，那么他们的乘积肯定大于100了。
因此，如果 是合数，那么它的因数对中至少有一个小的因数不大于 。所以我们只需要检查 2 到 的整数即可判断 是否为质数。
举例：如果100的话，我们只要检查(2,3,4,5,6,7,8,9,10)就可以了。
与算法二相比，判断次数大幅减少。
4. 算法四：检查 2、3 和 (质数判断法)
为什么是 质数判断法？
我们知道，所有的整数都可以表示为以下六种形式之一：
其中 是一个整数。
可以被 6 整除，所以它不是质数（除非 ，但 0 不是质数）。 可以被 2 整除，所以它不是质数 可以被 3 整除，所以它不是质数 可以被 2 整除，所以它不是质数 可以被 5 整除，所以它不是质数（除非 ，但 5 是质数） 因此，只有 和 （也就是 ）可能是质数。
通过算法三，我们已经知道质数的判断范围可以缩小到 。只要判断这个范围的质数就可以了，而大于 3 的质数一定是 的形式，所以我们只需要检查 2、3 和不超过 的 就可以了。
★因为这个范围的合数已经被这个合数对应的质因数排除掉了，所以我们只需要检查 的数是否能整除 。 比如100的话，我们只要检查2、3和(5,7,11,13,17,19,23,25,29,31)就可以了。 4 就不用检查,因为前面已经检查了2了，6就不用检查了，因为前面已经检查了2，3了
举例：判断 997 时，实际检查的除数是：
2、3、5、7、11、13、17、19、23、25、29、31
共进行 12 次取模运算。 这里要特别注意：大于 3 的质数一定是 ，但 不一定是质数。 例如 25 可以写成 ，但它仍然是合数。因此，算法不能把所有 直接当成质数，只是把它们作为可能的因子进行检查。
所以这个算法还有改进的空间。
三、数学建模
问题分析
输入：一个待判断的正整数 n输出： n是否为质数，以及每种算法执行取模判断的次数对比标准：每执行一次 n % d == 0，判断次数增加 1
模型步骤
分别实现四个质数判断函数 每次尝试一个可能的因子时，将计数器 count加 1如果找到因子，立即停止并返回结果 使用同一个数 997 测试四种算法 比较四种算法的判断次数
四、Python 代码实现
import math
defis_prime_1(n):
"""算法一：检查 2 到 n-1。"""
if n < 2:
returnFalse, 0
count = 0# 计数器，记录计算的次数
for divisor in range(2, n): # 从 2 到 n-1 进行检查
count += 1
if n % divisor == 0: # 如果 n 能被 divisor 整除，说明 n 不是质数
returnFalse, count
returnTrue, count # 如果没有找到任何 divisor 能整除 n，说明 n 是质数
defis_prime_2(n):
"""算法二：检查 2 到 n/2。"""
if n < 2:
returnFalse, 0
count = 0# 计数器，记录计算的次数
for divisor in range(2, n // 2 + 1): # 从 2 到 n/2 进行检查
count += 1
if n % divisor == 0: # 如果 n 能被 divisor 整除，说明 n 不是质数
returnFalse, count
returnTrue, count # 如果没有找到任何 divisor 能整除 n，说明 n 是质数
defis_prime_3(n):
"""算法三：检查 2 到 sqrt(n)。"""
if n < 2: # 0 和 1 都不是质数
returnFalse, 0
count = 0# 计数器，记录计算的次数
#math.isqrt(num) 函数返回 n 的整数平方根，即不大于 sqrt(n) 的最大整数
for divisor in range(2, math.isqrt(n) + 1): # 从 2 到 isqrt(n) 进行检查
count += 1
if n % divisor == 0: # 如果 n 能被 divisor 整除，说明 n 不是质数
returnFalse, count
returnTrue, count # 如果没有找到任何 divisor 能整除 n，说明 n 是质数
defis_prime_4(n):
"""算法四：检查 2、3 和不超过 sqrt(n) 的 6k±1。"""
if n < 2: # 0 和 1 都不是质数
returnFalse, 0
count = 1# 计数器，记录计算的次数
if n % 2 == 0: # 如果 n 能被 2 整除，说明 n 不是质数（除非 n 是 2）
return n == 2, count
count += 1# 计数器，记录计算的次数
if n % 3 == 0: # 如果 n 能被 3 整除，说明 n 不是质数（除非 n 是 3）
return n == 3, count
divisor = 5# 从 5 开始检查，后续检查 6k±1 的数
limit = math.isqrt(n)
while divisor <= limit:
count += 1
if n % divisor == 0:
returnFalse, count
if divisor + 2 <= limit:
count += 1
if n % (divisor + 2) == 0:
returnFalse, count
divisor += 6# 检查下一个 6k±1 的数
returnTrue, count
number = 997
algorithms = [is_prime_1, is_prime_2, is_prime_3, is_prime_4]
print(f"待判断的数：{number}")
print("算法 判断结果 取模判断次数")
print("-" * 30)
for index, algorithm in enumerate(algorithms, start=1):
is_prime, count = algorithm(number)
result = "是质数"if is_prime else"不是质数"
print(f"算法{index}{result:<8}{count:>5}")
五、997 的实际测算结果
运行程序后输出：
待判断的数：997
算法 判断结果 取模判断次数
------------------------------
算法1 是质数 995
算法2 是质数 497
算法3 是质数 30
算法4 是质数 12
效率对比如下：
六、总结
通过数学分析，我们逐步优化了质数判断算法，从最简单的暴力算法到检查 的方法，效率得到了显著提升。对于较大的数，算法四的效率远远优于其他算法，尤其是当 很大时，这种差距会更加明显。
因此，在实际应用中，建议使用算法四来判断质数，尤其是当需要判断的数较大时。
但在实际中 还是可以进一步改进算法四的。
随机文章
-
10个月宝宝每天需要喝多少奶粉？
- 视频太多懒得看,Python调用Whisper提取字幕并总结,自媒体人狂喜
- 15k Star 优雅,Linux 桌面跑所有 Win 应用!
- 4python之web端上传获取不到conversation_id分析及解决
- 不知道 Python 能干什么?难怪你学不下去…
- kali-linux-2025.1a-installer|系统原版安装镜像文件
- 2026学术研究新标配:AI智能体+Python机器学习,你跟上了吗?
- 11.Ros2系列课程之-使用Python编写参数接口
- Python基础知识运算符与表达式
- 6个Python自学高质量APP
- 小白易懂的一张总结python最强大第三方库!