大O表示法中变量值与变量大小的区别：结合素性测试算法问题

核心定义差异 #

• x的值：就是变量存储的数值本身，比如x取100的时候，x的值就是100。
• x的大小：指计算机存储整数x需要的二进制位长度，也叫位长。对于正整数x，位长的计算公式是floor(log₂x) + 1，还是以x=100为例，log₂100≈6.64，所以x的大小是7位。

结合题目代码的复杂度分析 #

你给出的暴力素性测试代码，最坏情况（x本身是素数的时候）要循环x-2次，时间复杂度按x的值来算是O(x)，属于线性复杂度。
但如果我们把复杂度用x的大小（位长n）来换算的话，因为n位的二进制数最大可以表示2ⁿ-1，所以x≈2ⁿ，代入上面的复杂度就得到O(2ⁿ)，这是典型的指数级复杂度。也就是说，相对于x的大小（位长）来说，这个算法的运行时间是指数级的，所以题目正确答案是C。

其他错误选项说明 #

• 选项A错误：密码学场景下常用的素数都是2048位甚至更长的大素数，这个暴力算法要跑2^2048次，完全不可能在可接受的时间内跑完，没有实用性。
• 选项B错误：相对于x的值来说，算法的复杂度是线性的O(x)，不是指数级。
• 选项D错误：代码仅没有处理x<2的边界情况，核心素性判断逻辑没有致命错误。

内容的提问来源于stack exchange，提问作者venkysmarty