Python 质数判断（建议收藏）

Python 质数判断：从零开始掌握基础算法

在编程学习的道路上，质数是一个绕不开的经典问题。它不仅是数学中的基础概念，也是检验算法思维的“试金石”。今天我们就来深入探讨 Python 质数判断的多种实现方式，帮助你从入门到进阶，真正掌握这一核心技能。

质数，指的是大于 1 且只能被 1 和自身整除的自然数。比如 2、3、5、7、11 都是质数，而 4、6、8、9 显然不是。在 Python 中实现质数判断，看似简单，实则蕴含了算法优化的精髓。接下来，我们就一步步揭开它的面纱。

什么是质数？为什么它重要？

想象一下，质数就像数字世界里的“原子”——它们是构成所有自然数的最小单位。任何一个大于 1 的自然数，都可以唯一地分解为若干个质数的乘积（这就是算术基本定理）。这个特性让质数在密码学、数据加密等领域具有不可替代的作用。

在编程中，质数判断常用于：

• 算法竞赛题目
• 数学建模
• 验证输入合法性
• 生成加密密钥

而 Python 质数判断，正是掌握这些应用的基础。我们先从最直观的方法开始。

最基础的判断方法：暴力遍历

最直接的思路是，对一个给定的数 n，从 2 开始逐个尝试能否整除它。如果在 2 到 n-1 的范围内找到一个能整除 n 的数，那它就不是质数。

def is_prime_basic(n):
    # 如果 n 小于等于 1，则不是质数
    if n <= 1:
        return False
    
    # 从 2 到 n-1 遍历，看是否有能整除 n 的数
    for i in range(2, n):
        if n % i == 0:
            return False  # 找到因数，说明不是质数
    
    return True  # 没找到因数，是质数

代码注释说明：

• n <= 1：质数定义要求大于 1，所以直接排除。
• range(2, n)：从 2 开始，一直到 n-1，检查是否能整除。
• n % i == 0：如果余数为 0，说明 i 是 n 的因数。
• 一旦发现因数，立刻返回 False，提高效率。
• 若循环结束仍未返回，说明没有因数，返回 True。

这个方法逻辑清晰，适合初学者理解。但缺点也很明显：时间复杂度是 O(n)，当 n 很大时，效率极低。

优化一：只需检查到 √n

你有没有发现，如果一个数 n 有一个大于 √n 的因数，那它必然有一个对应的小于 √n 的因数？比如 12 = 3 × 4，其中 3 < √12 ≈ 3.46，而 4 > √12。

所以，我们只需要检查从 2 到 √n 的数即可。如果这些数中没有因数，那 n 就是质数。

import math

def is_prime_optimized(n):
    # 小于等于 1 的数不是质数
    if n <= 1:
        return False
    
    # 只需检查到 sqrt(n)，因为因数成对出现
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            return False  # 找到因数，不是质数
    
    return True  # 未找到因数，是质数

代码注释说明：

• math.sqrt(n)：计算 n 的平方根。
• int(math.sqrt(n)) + 1：因为 range 是左闭右开，需要 +1 保证包含 √n。
• 例如 n = 16，√16 = 4，只需检查 2 到 4。
• 时间复杂度降到 O(√n)，效率大幅提升。

这个优化是质数判断中的“第一道关卡”，几乎所有的进阶方法都建立在它之上。

优化二：跳过偶数，提升效率

除了 2 以外，所有质数都是奇数。因此，我们可以在判断时跳过所有偶数，只检查 2 和奇数。

def is_prime_even_skip(n):
    # 处理特殊情况
    if n <= 1:
        return False
    if n == 2:
        return True  # 2 是唯一的偶数质数
    if n % 2 == 0:
        return False  # 偶数且大于 2，不是质数
    
    # 只检查奇数，从 3 开始，步长为 2
    for i in range(3, int(math.sqrt(n)) + 1, 2):
        if n % i == 0:
            return False
    
    return True

代码注释说明：

• n == 2：特例，直接返回 True。
• n % 2 == 0：排除所有其他偶数。
• range(3, ..., 2)：从 3 开始，每次加 2，只遍历奇数。
• 这样可以将循环次数减半，效率再提升一倍。

这个技巧在实际项目中非常实用，尤其是当需要判断大量数字时。

实际应用：筛选指定范围内的所有质数

掌握了单个判断方法后，我们可以进一步扩展，写出“埃拉托斯特尼筛法”（Sieve of Eratosthenes），用于高效筛选出 1 到 n 之间的所有质数。

def sieve_of_eratosthenes(n):
    # 创建布尔数组，初始化为 True，表示假设都是质数
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False  # 0 和 1 不是质数
    
    # 从 2 开始，筛除所有倍数
    for i in range(2, int(math.sqrt(n)) + 1):
        if is_prime[i]:
            # 标记 i 的所有倍数为非质数
            for j in range(i * i, n + 1, i):
                is_prime[j] = False
    
    # 收集所有质数
    primes = [i for i in range(2, n + 1) if is_prime[i]]
    return primes

代码注释说明：

• is_prime = [True] * (n + 1)：创建一个长度为 n+1 的列表，索引代表数字。
• is_prime[0] = is_prime[1] = False：明确排除 0 和 1。
• range(2, int(math.sqrt(n)) + 1)：只需筛到 √n。
• j in range(i * i, n + 1, i)：从 i² 开始，因为小于 i² 的倍数已被更小的质数筛过。
• is_prime[j] = False：标记合数。
• 最后通过列表推导式收集所有质数。

时间复杂度：O(n log log n)，远优于逐个判断的 O(n√n)。适合批量处理。

性能对比：不同方法效率测试

为了直观感受优化效果，我们来做一个小测试，判断 10000 以内所有质数所需时间。

这个表格展示了算法优化的巨大威力。在实际开发中，选择合适的方法，往往比写复杂代码更重要。

常见误区与注意事项

在实现 Python 质数判断时，初学者常犯几个错误：

1. 忘记处理 n == 2 的情况：2 是唯一的偶数质数，不能遗漏。
2. 循环边界错误：range(2, n) 会漏掉 n-1，应使用 range(2, int(math.sqrt(n)) + 1)。
3. 重复计算平方根：每次循环都调用 math.sqrt(n) 会降低效率，应提前计算。
4. 忽略负数或小数输入：在实际应用中，需增加输入校验。

建议在正式代码中加入类型检查和边界判断：

def safe_is_prime(n):
    if not isinstance(n, int):
        raise TypeError("输入必须是整数")
    if n < 0:
        return False
    if n <= 1:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    
    for i in range(3, int(math.sqrt(n)) + 1, 2):
        if n % i == 0:
            return False
    return True

总结：从基础到进阶的完整路径

通过今天的学习，我们从最简单的暴力法出发，逐步引入了平方根优化、偶数跳过、筛法等高级技巧。每一步都建立在前一步的基础上，体现了“先实现，再优化”的编程哲学。

Python 质数判断不仅是一个算法练习，更是培养逻辑思维和代码优化能力的绝佳范例。无论你是初学者，还是希望提升算法能力的中级开发者，掌握这些方法都将让你在面对类似问题时更加从容。

记住：没有“最好”的方法，只有“最适合”当前场景的方法。在实际项目中，根据数据规模和频率选择合适策略，才是真正的高手之道。

最后，如果你正在学习编程，不妨动手写一个程序，判断 1 到 1000 中的所有质数，并对比不同方法的执行时间。实践，才是掌握一切技能的唯一途径。