91是质数吗?3行代码搞定性能优化

别被官方文档那几十页的数学定义吓住，抓不住重点？其实判断91是不是质数，核心就在一个循环里。很多初学者卡在“试除范围”上，导致代码跑得慢，这正是性能优化的关键切入点。咱们直接上干货，用Python几行代码把这事说明白，顺便带你避开那些常见的坑。

概念速懂：质数到底长啥样

很多人对质数的理解停留在“只能被1和它本身整除”。这话没错，但太笼统，容易让你在写代码时漏掉边界情况。

从机器学习的角度看，质数分布就像是一种稀疏特征。在训练模型时，我们需要快速筛选出这些“特殊样本”。如果每次判断都要从头试到末尾，那数据量一大，训练时间直接爆炸。

91这个数字很有代表性。它看起来挺大，不像2、3、5那样一眼假。很多人直觉认为它是质数，因为它不能被2、3、5整除。但真相是，91 = 7 × 13。所以，91不是质数。

这里有个核心逻辑：判断一个数 \(n\) 是否为质数，不需要试除到 \(n-1\)。只要试除到 \(\sqrt{n}\) 就够了。为什么？因为如果 \(n = a \times b\)，且 \(a < b\)，那么 \(a\) 一定小于 \(\sqrt{n}\)。如果 \(\sqrt{n}\) 以内都没有因子，那 \(n\) 就是质数。

这个数学原理，直接决定了代码的性能上限。很多初学者写的代码是 for i in range(2, n)，当 \(n\) 是百万级时，这简直是灾难。而优化后的代码是 for i in range(2, int(n**0.5) + 1)，效率提升几十倍。这就是所谓的“算法层面的性能优化”，比单纯升级硬件管用得多。

对于培训机构学员来说，这个知识点不仅是数学题，更是编程思维的试金石。它考察的是你能否将数学逻辑转化为高效的计算机指令。在面试中，如果被问到“如何快速判断大数是否为质数”，答出“试除到平方根”这一步，基本就及格了。

环境准备：Python 3.x 基础配置

咱们用 Python 来演示，因为它语法简洁，适合快速验证逻辑。你需要一个支持 Python 3.8+ 的环境。

如果你还在用 Python 2，赶紧升级。Python 2 已经停止维护，很多库都不再支持。在命令行输入 python --version 检查一下。

不需要安装复杂的第三方库。判断质数是基础操作，标准库 math 模块就够用。当然，如果你打算处理超大数（比如密码学级别），可能需要 gmpy2 这样的库，但咱们今天的目标是 91，标准库完全 hold 住。

建议你在 VS Code 或 PyCharm 里新建一个文件，命名为 is_prime.py。保持环境干净，不要混入其他无关代码。这样在调试时，报错信息会更清晰。

有些学员喜欢用 Jupyter Notebook 做练习，这也可以。但要注意，Jupyter 的执行顺序是线性的，确保你在运行判断代码前，已经定义了函数。如果在同一单元格里定义函数和调用函数，有时会因为内核缓存问题出现“NameError”，这时候记得重启内核再运行。

另外，提醒一点：变量命名要规范。不要用 a、b 这种单字母变量，除非是在非常简短的循环里。我们要用 number、factor、is_prime 这样的名字。这是工程习惯，也是未来团队协作的基础。很多初级开发者因为变量命名混乱，导致代码可读性极差，重构时痛苦不堪。

核心语法：从暴力到优化

先看最“笨”的写法。虽然它效率低，但逻辑最直观，适合初学者理解流程。

def is_prime_bruteforce(n):"""暴力法判断质数时间复杂度: O(n)"""if n <= 1:return Falsefor i in range(2, n):if n % i == 0:return Falsereturn True# 测试 91
print(is_prime_bruteforce(91))  # 输出: False

这段代码的逻辑是：从 2 开始，一直试除到 \(n-1\)。一旦发现能整除，立刻返回 False。如果循环结束都没找到因子，返回 True。

跑一下，输出是 False。正确，但慢。当 \(n=91\) 时，它循环了 89 次。如果 \(n=10,000,000\)，它要循环一千万次。这在性能上是不可接受的。

接下来，上优化版。核心改动就一处：循环上限改为 \(\sqrt{n}\)。

import mathdef is_prime_optimized(n):"""优化法判断质数时间复杂度: O(sqrt(n))"""if n <= 1:return False# 关键优化: 只试除到平方根limit = int(math.sqrt(n)) + 1for i in range(2, limit):if n % i == 0:return Falsereturn True# 测试 91
print(is_prime_optimized(91))  # 输出: False

这里引入了 math 模块的 sqrt 函数。int(math.sqrt(n)) 会截断小数部分。比如 \(\sqrt{91} \approx 9.539\)，取整后是 9。我们加 1 变成 10，是为了确保覆盖边界。range(2, 10) 会生成 2 到 9 的整数。

为什么加 1 很重要？假设 \(n\) 是完全平方数，比如 49。\(\sqrt{49} = 7\)。如果不加 1，range(2, 7) 只生成到 6，就漏掉了 7 这个因子，导致误判 49 是质数。加 1 后，range(2, 8) 包含 7，正确判断 49 不是质数。

这就是细节决定成败的地方。很多博客教程会忽略这个 +1，导致代码在特定输入下出错。作为资深从业者，我要强调：边界条件是代码健壮性的生命线。

再进一步，我们可以做一点小优化。除了 2 以外，所有的质数都是奇数。所以，我们可以先排除偶数，然后只试除奇数。

def is_prime_advanced(n):"""进阶法: 排除偶数，只试除奇数时间复杂度: O(sqrt(n)/2)"""if n <= 1:return Falseif n == 2:return Trueif n % 2 == 0:return False# 只试除奇数limit = int(math.sqrt(n)) + 1for i in range(3, limit, 2):if n % i == 0:return Falsereturn Trueprint(is_prime_advanced(91))  # 输出: False

range(3, limit, 2) 表示从 3 开始，步长为 2，即 3, 5, 7, 9... 这样循环次数直接减半。虽然对于 91 这种小数，提升不明显，但对于大数，效果显著。

完整代码示例：实战演练

咱们把前面几个版本整合起来，做一个完整的测试脚本。不仅测试 91，还要测试一些边界情况，比如 1、2、4、97 等。

import math
import timedef is_prime_v1(n):"""暴力法"""if n <= 1:return Falsefor i in range(2, n):if n % i == 0:return Falsereturn Truedef is_prime_v2(n):"""平方根优化法"""if n <= 1:return Falselimit = int(math.sqrt(n)) + 1for i in range(2, limit):if n % i == 0:return Falsereturn Truedef is_prime_v3(n):"""奇数优化法"""if n <= 1:return Falseif n == 2:return Trueif n % 2 == 0:return Falselimit = int(math.sqrt(n)) + 1for i in range(3, limit, 2):if n % i == 0:return Falsereturn True# 测试用例
test_cases = [1, 2, 4, 9, 13, 91, 97, 100, 1000003]print(f"{'Number':<10} {'V1':<6} {'V2':<6} {'V3':<6} {'V1 Time':<10} {'V3 Time':<10}")
print("-" * 48)for n in test_cases:start_v1 = time.time()result_v1 = is_prime_v1(n)end_v1 = time.time()time_v1 = end_v1 - start_v1start_v3 = time.time()result_v3 = is_prime_v3(n)end_v3 = time.time()time_v3 = end_v3 - start_v3# 格式化输出，保留6位小数print(f"{n:<10} {str(result_v1):<6} {str(is_prime_v2(n)):<6} {str(result_v3):<6} {time_v1:.6f} {time_v3:.6f}")

运行这段代码，你会看到类似这样的输出：

Number     V1     V2     V3     V1 Time    V3 Time   
------------------------------------------------
1          False  False  False  0.000001   0.000000
2          True   True   True   0.000000   0.000000
4          False  False  False  0.000001   0.000000
9          False  False  False  0.000001   0.000000
13         True   True   True   0.000000   0.000000
91         False  False  False  0.000002   0.000000
97         True   True   True   0.000001   0.000000
100        False  False  False  0.000001   0.000000
1000003    True   True   True   0.001200   0.000010

注意看最后一行，\(1,000,003\) 是一个质数。V1 版本耗时约 0.0012 秒，V3 版本耗时约 0.00001 秒。性能提升了 100 倍以上。这就是算法优化的威力。

在机器学习场景中，如果你需要处理百万级特征值的质数标记，这种性能差异会导致训练时间从小时级缩短到分钟级。这就是为什么大厂面试会问“如何优化质数判断”，因为它直接关联到数据处理管道的效率。

另外，注意 time.time() 的使用。它返回的是系统当前时间戳，单位是秒。精度到微秒级别，足够我们做这种小规模的基准测试。如果需要更高精度的基准测试，可以使用 time.perf_counter()，它能提供更高精度的计时器，适合测量短时间间隔。

常见报错：避坑指南

在实际开发中，判断质数的代码虽然短，但坑不少。这里列举三个最常见的错误。

坑一：忘记处理小于 2 的数

很多代码只写了 for i in range(2, ...)，但没判断 \(n < 2\)。对于 \(n=1\)，循环不会执行，直接返回 True，这是错误的。1 既不是质数也不是合数，必须显式返回 False。

坑二：整数溢出（在 C/C++ 中）

在 Python 中，整数没有固定长度，不会溢出。但在 C/C++ 或 Java 中，如果你用 int 类型存储 \(n\)，当 \(n\) 很大时，n * n 可能会溢出。虽然 Python 没这个问题，但如果你以后转 C++，这点要注意。在 C++ 中，判断平方根时，应该用 long long 或者避免直接乘方，改用 i * i <= n 来判断循环终止条件，这样更通用。

坑三：浮点数精度问题

有些开发者用 i * i <= n 代替 i <= sqrt(n)，避免开方运算。这本身是个好技巧，因为整数乘法比浮点开方快。但要注意，如果 \(n\) 非常大，i * i 可能会超出整数范围（在非 Python 语言中）。在 Python 中，这没问题，因为 Python 自动处理大整数。

坑四：混淆质数与偶数

有些新手会写 if n % 2 == 0: return False，然后忘记排除 \(n=2\) 的情况。2 是唯一的偶数质数，必须特殊处理。如果直接返回 False，就会把 2 误判为非质数。

为了验证代码的鲁棒性，建议你在单元测试中加入这些边界用例：1, 2, 3, 4, 9, 25, 49, 100, 999983 (大质数), 999984 (大合数)。用这些用例跑一遍，确保你的函数在所有情况下都正确。

在 Python 中，可以使用 pytest 框架来写自动化测试。比如：

import pytest
from is_prime_module import is_prime_advanceddef test_prime_numbers():assert is_prime_advanced(2) == Trueassert is_prime_advanced(3) == Trueassert is_prime_advanced(97) == Truedef test_non_prime_numbers():assert is_prime_advanced(1) == Falseassert is_prime_advanced(4) == Falseassert is_prime_advanced(91) == Falseassert is_prime_advanced(100) == False

这样，每次修改代码后，运行 pytest 就能快速回归测试，确保没有引入新的 Bug。这是专业开发者的基本素养。