Python 算法实战：从初级到骨灰级的素数判定函数

1. 素数判定的基本逻辑

素数（Prime Number）是指在大于 1 的自然数中，除了 1 和它本身以外不再有其他因数的数。

在编写函数时，新手最容易在边界条件（Corner Cases）上栽跟头。最常见的误区是：

• 漏掉 2 和 3：因为它们是最小的两个素数，且 2 是唯一的偶素数。
• 忽略效率：对大数字进行全量循环，导致 O(n) 的低效表现。

2. 演进方案：从 到

方案 A：标准平方根法（基础款）

通过数学证明，如果一个数 不是素数，它必然有一个因子小于或等于 。

import math

def is_prime_v1(n):
    if n <= 1: return False
    # 循环范围 [2, sqrt(n)]
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            return False
    return True

分析：虽然逻辑正确，但它对每一个数字（包括大量的偶数）都进行了取模运算。

方案 B：6k ± 1 高效法（进阶款）

这是目前单数判定中最高效的启发式算法之一。其核心数学原理是：除了 2 和 3，所有的素数都可以表示为 的形式。

• 原理：任何整数都可以表示为 。
• 都能被 2 整除。
• 能被 3 整除。
• 只剩下 和 （即 ）可能是素数。

3. 最终优化实现

以下是结合了边界处理与 6k 优化的完整代码：

import math

def is_prime(n):
    """
    高效判断一个数是否为素数
    """
    # 1. 处理小于等于 3 的特殊情况
    if n <= 3:
        return n > 1
    
    # 2. 排除能被 2 或 3 整除的数
    # 这一步可以瞬间过滤掉 2/3 的非素数数据
    if n % 2 == 0 or n % 3 == 0:
        return False
    
    # 3. 核心循环：步长为 6，只检查 6k ± 1
    # 初始 i = 5 (即 6*1 - 1)，下一次循环 i = 11 (即 6*2 - 1)
    limit = int(math.sqrt(n)) + 1
    for i in range(5, limit, 6):
        # 检查 i (6k-1) 和 i+2 (6k+1)
        if n % i == 0 or n % (i + 2) == 0:
            return False
            
    return True

4. 优化点解析

1. 空间换时间：通过显式处理 2 和 3 的倍数，我们在进入昂贵的 for 循环之前，就已经排除掉了约 66.6% 的合数。
2. 步进优化：将 range 的步长设为 6。在每一次循环中，我们同时测试 和 。这意味着我们的迭代次数只有标准方法的 1/3。
3. 计算优化：math.sqrt(n) 在循环外计算一次，避免在每次循环迭代时重复计算开方。

5. 总结与性能建议

如果你的应用场景需要批量生成大量素数（例如 1 到 1000 万之间的所有素数），那么单次判定就不再合适，此时建议研究 埃拉托斯特尼筛法（Sieve of Eratosthenes）。