python必背源代码判断素数代码

素数（又称质数）是指在大于 1 的自然数中，除了 1 和它本身以外不再有其他因数的数。判断一个正整数是否为素数，是 Python 编程考级、求职面试和日常算法编写中出现频次极高的基础考点。最简洁、最标准且实用的必背解法是基于平方根试除法的函数实现，它利用因数成对分布的数学特性，将检测时间复杂度从 O(n) 优化至 O(√n)。本文给出这一段必须熟记的核心源代码，并逐步拆解代码实现细节、数学推导证明、6k±1 进阶跳步优化以及初学者常见的边界误区。

一、核心必背源代码：平方根试除法标准实现

在 Python 中判断一个数 n 是否为素数，最规范、不易出错的标准函数如下。这段代码结构紧凑，适合在任何需要素数判断的场景中直接使用或默写背诵：

def is_prime(n):
    """判断正整数 n 是否为素数，返回布尔值 True 或 False"""
    if n <= 1:
        return False
    for i in range(2, int(n**0.5) + 1):
        if n % i == 0:
            return False
    return True

代码逐行拆解与执行逻辑：

• 第 3～4 行（边界防御）：if n <= 1: return False。素数的数学定义限定在“大于 1 的自然数”。0、1 以及所有负整数均不是素数，直接在此拦截并返回 False，防止进入后续循环。
• 第 5 行（试除区间控制）：for i in range(2, int(n**0.5) + 1):。从最小的素数 2 开始遍历因数，上限截断在 int(n**0.5) + 1。这里 n**0.5 即对 n 取开平方根。因为 Python 的 range(start, stop) 生成的是左闭右开区间 [start, stop)，所以必须在取整后主动加上 1，才能保证把恰好等于 √n 的边界数（例如 n = 25 时的因数 5）纳入试除范围。
• 第 6～7 行（因数整除测试）：if n % i == 0: return False。在循环过程中，一旦发现 n 能被当前的 i 整除（余数为 0），就证明找到了除了 1 和自身以外的因数，此时可直接断定 n 为合数，函数立即返回 False 退出。
• 第 8 行（确认素数）：return True。如果 range 范围内的所有候选数都无法整除 n，说明 n 不存在非平凡因数，此时正常跳出循环并返回 True。

完整调用示例与验证：

可以将上述函数与测试数据组合运行，通过遍历一组常见边界值与典型数值来验证其逻辑正确性：

# 测试脚本示例：检验各类典型输入
test_cases = [0, 1, 2, 3, 4, 17, 25, 97, 100]
for val in test_cases:
    result = is_prime(val)
    print(f"数字 {val:>3} -> {'是素数' if result else '不是素数'}")

二、数学原理：为什么只需试除到 √n？

许多初学者在刚学习素数判断时，往往习惯直接写出 range(2, n)，也就是从 2 一直测试到 n - 1。虽然这种朴素试除法在逻辑上也是正确的，但当 n 变大时会产生大量无意义的计算。将上限收缩到 √n 的数学依据如下：

假设正整数 n 是一个合数，那么根据因数分解定义，它必然可以表示为两个大于 1 的自然数相乘的形式：

反证推导：假设 a 和 b 都严格大于 √n（即 a > √n 且 b > √n），那么将两者相乘，必然得到：

a × b > √n × √n = n

这与已知的前提 a × b = n 发生了矛盾。因此，这两个因数不可能同时大于 √n，其中较小的那一个因数 a 必然小于或等于 √n。

这一推论带来的实际操作结论是：如果我们在区间 [2, √n] 之内没有找到任何一个能整除 n 的因数，那么在区间 (√n, n) 之内也绝对不可能单独存在能整除 n 的大因数（因为大因数一旦存在，必有一一对应的较小因数落在前半段）。因此，超出 √n 之后的所有数字都可以安全剪枝，不需要再做任何检验。

三、进阶必背代码：6k±1 步长优化法

在基础平方根试除法中，我们依然对 [2, √n] 之间的每个连续整数进行了试除，其中包括了大量的偶数（如 4、6、8）以及 3 的倍数（如 9、15）。如果能在循环中跳过这些显而易见的合数，效率将进一步大幅提升。数论中的 6k±1 法则 为我们提供了绝佳的跳步依据。

模 6 余数与素数分布规律：

任意一个自然数除以 6，其余数只可能是 0、1、2、3、4、5 中的一个。因此所有自然数都可以归入以下六种形式：

• 6k：等于 2 × (3k)，能被 2 和 3 整除，除 0 外均为合数；
• 6k + 2：等于 2 × (3k + 1)，是偶数，除 2 以外均为合数；
• 6k + 3：等于 3 × (2k + 1)，能被 3 整除，除 3 以外均为合数；
• 6k + 4：等于 2 × (3k + 2)，是偶数，均为合数；
• 6k + 1 与 6k + 5（即 6k - 1）：既不是 2 的倍数，也不是 3 的倍数，所有大于 3 的素数必然且只能分布在这两类数中。

6k±1 优化版源代码：

根据这一规律，我们可以先通过常数时间特判排除 2、3 及其倍数，随后让指针从 5 开始，以 6 为步长递增，每次只测试 i（即 6k-1）和 i + 2（即 6k+1）：

def is_prime_fast(n):
    """进阶必背：6k±1 步长优化的快速素数判定函数"""
    if n <= 1:
        return False
    if n <= 3:
        return True
    # 排除能被 2 或 3 整除的数
    if n % 2 == 0 or n % 3 == 0:
        return False
    # 从 5 开始（对应 6*1 - 1），每次跳步 +6
    i = 5
    while i * i <= n:
        if n % i == 0 or n % (i + 2) == 0:
            return False
        i += 6
    return True

相比基础试除法，该函数在进入核心循环后，每 6 个数只检测 2 次，跳过了 4 次无效判断，循环内部计算量直接缩减了 66.7%。同时代码中采用 i * i <= n 替代浮点开方，完全由纯整数运算构成，既稳健又迅速。

四、常见误区与容易混淆的说法辨析

在素数判断代码编写中，有一些看似合理却潜藏逻辑缺陷的写法。理清这些问题能够帮助我们在考试或实战中彻底避免扣分：

1. 误区：range(2, int(n**0.5)) 漏写 + 1

现象分析：当输入完全平方数 n = 4 时，int(4**0.5) = 2。此时 range(2, 2) 生成的是一个空序列，for 循环一次都不会执行，代码直接穿透到末尾返回 True！这就导致 4、9、25 等完全平方数被系统误判为素数。必须写成 range(2, int(n**0.5) + 1)，或者使用 while i * i <= n 这种不依赖开区间的循环条件。

2. 辨析：int(n**0.5) + 1 与 i * i <= n 哪个更好？

两种写法均很常见。在实际选用时需要看具体侧重点：

• range(2, int(n**0.5) + 1) 的优点：结构紧凑，配合 for 循环自增，代码行数最少，写起来最顺手，非常适合课堂测试与普通编码。
• while i * i <= n 的优点：纯整数乘法运算，完全规避了浮点数开方。在 Python 中，当 n 达到 $10^{15}$ 以上时，n**0.5 转换为 float 会因为尾数位数限制丢失精度，导致上限计算发生偏差。因此，在算法竞赛、严格面试或大整数场景中，采用 while i * i <= n 更加鲁棒和专业。

3. 误区：仅用 if n == 1: return False 做特判

许多初学代码只拦截了 1，写出类似 if n == 1: return False 的逻辑。但如果传入参数包含 0 或负数（例如 -7），在 Python 中 range(2, ...) 会直接产生空区间，导致函数把负数错误识别为素数。素数的严格数学定义是“大于 1 的自然数”，任何防御代码都必须使用小于等于号：if n <= 1: return False。

4. 辨析：“必背试除法是否能够判断上百位的超大数字？”

必须明确该算法的适用边界。无论是基础试除法还是 6k±1 优化，它们的时间复杂度都是 O(√n)。在常见考试和日常开发中（$n \le 10^{12}$），毫秒级即可完成。但如果数字达到现代密码学（如 RSA 加密算法）中常见的 100 位或 200 位大数，$\sqrt{n}$ 依然有几十位到上百位，需要执行 $10^{50}$ 次以上的循环，世界上最强的超算也无法在现实时间内跑完。处理超大规模数字时，必须转向概率素性测试算法（例如 Miller-Rabin 算法）。试除法是为中小规模数据量身打造的确定性必背代码。

五、实用衍生操作与技术选型总结

掌握了 is_prime 基础函数之后，在实际开发中往往需要结合具体场景进行灵活运用：

1. 批量提取范围内的所有素数

借助 Python 优雅的列表推导式，我们可以直接组合单数判断函数，用单行代码筛选出指定区间内的全部素数：

# 获取 1 到 100 之间的全部素数列表
primes_100 = [x for x in range(1, 101) if is_prime(x)]
print("100以内的素数：", primes_100)

2. 单数测试与区间筛选的技术选型分水岭

在面临批量素数生成需求时，需要注意算法选择的分水岭：

• 判定单个数的素性（或者数字总量较少）：无脑选用本文的平方根试除法或 6k±1 优化法，空间复杂度为 O(1)，无需任何辅助数组。
• 批量求出极大规模区间 [2, N] 内的所有素数（如 N ≥ 10⁵）：如果继续对每个数单独调用 is_prime，整体时间复杂度为 O(N√N)。此时应当选择以空间换时间的埃拉托斯特尼筛法（Sieve of Eratosthenes）或欧拉线性筛法，将复杂度大幅降低至 O(N log log N)。