Python实战：如何高效求解指定范围内的素数（附完整代码与性能优化）

共计 1106 个字符，预计需要花费 3 分钟才能阅读完成。

背景介绍

素数（质数）在密码学、数学研究等领域有广泛应用。对于编程新手来说，求解指定范围内的素数常遇到以下问题：

• 算法效率低下，当范围较大时程序运行缓慢
• 边界条件处理不当（如忽略 1 不是素数）
• 代码结构混乱，可读性差

技术方案：试除法优化

判断素数的经典方法是试除法，即判断该数是否能被 2 到其平方根之间的整数整除。优化思路：

1. 只需检查到平方根即可（数学原理：若 n 有大于 sqrt(n) 的因子，则必有小于 sqrt(n) 的对应因子）
2. 跳过偶数判断（除了 2 以外，偶数都不可能是素数）
3. 使用函数封装判断逻辑，提高代码复用性

完整代码实现

def is_prime(num):
    """判断是否为素数"""
    if num <= 1:  # 1 不是素数
        return False
    if num == 2:  # 2 是唯一偶素数
        return True
    if num % 2 == 0:  # 排除其他偶数
        return False
    # 只需检查到平方根
    for i in range(3, int(num**0.5)+1, 2):
        if num % i == 0:
            return False
    return True

# 主程序
m, n = map(int, input("请输入范围 m n（用空格分隔）:").split())
prime_list = []
count = 0

for num in range(m, n+1):
    if is_prime(num):
        prime_list.append(str(num))
        count += 1

# 输出结果
print(' '.join(prime_list))
print(f'count = {count}')

性能优化分析

1. 时间复杂度对比：
2. 原始试除法：O(n√n)
3. 优化后算法：O(n√n/2)（跳过偶数检查）
4. 进一步优化方向：
5. 预先生成素数表（埃拉托斯特尼筛法）
6. 使用 Miller-Rabin 概率测试（适合极大数判断）

避坑指南

常见错误及解决方案：

• 错误 1：忘记处理 1 不是素数的情况

• 解决方法：在判断函数开头添加 if num <= 1: return False

• 错误 2：范围包含 n 时错误使用 range(m,n)

• 正确做法：range(m, n+1)

• 错误 3：未优化偶数判断导致性能浪费

• 建议：单独处理 2 后直接跳过其他偶数

实践建议

尝试扩展以下功能：

1. 输出素数的同时计算它们的和
2. 将结果写入文件而不仅打印到屏幕
3. 增加异常处理（如输入非数字、m>n 等情况）
4. 可视化输出（如用 matplotlib 绘制素数分布）

结语

通过本文的学习，你应该已经掌握了：
– 素数判断的核心算法
– Python 函数封装的最佳实践
– 基本的算法优化思路
建议动手实现文中代码，并尝试扩展功能来巩固学习效果。在实际项目中，根据具体需求选择适合的算法——对小范围素数判断，优化后的试除法已经足够；但对极大数或超大数据集，可能需要更高级的算法。