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

1. 素数判定的基本逻辑#

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

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

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

2. 演进方案：从到#

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

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

1
import math
2

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

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

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

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

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

3. 最终优化实现#

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

1
import math
2

3
def is_prime(n):
4
    """
5
    高效判断一个数是否为素数
6
    """
7
    # 1. 处理小于等于 3 的特殊情况
8
    if n <= 3:
9
        return n > 1
10

11
    # 2. 排除能被 2 或 3 整除的数
12
    # 这一步可以瞬间过滤掉 2/3 的非素数数据
13
    if n % 2 == 0 or n % 3 == 0:
14
        return False
15

16
    # 3. 核心循环：步长为 6，只检查 6k ± 1
17
    # 初始 i = 5 (即 6*1 - 1)，下一次循环 i = 11 (即 6*2 - 1)
18
    limit = int(math.sqrt(n)) + 1
19
    for i in range(5, limit, 6):
20
        # 检查 i (6k-1) 和 i+2 (6k+1)
21
        if n % i == 0 or n % (i + 2) == 0:
22
            return False
23

24
    return True

4. 优化点解析#

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

5. 总结与性能建议#

算法版本	1,000,000 次判定耗时 (参考)	推荐场景
全量循环	极慢	仅限教学演示
平方根法	较快	通用情况
6k ± 1 法	极快	大数判定/工程实践

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