素性问题时间复杂度疑问：朴素素性检测算法O(n²10ⁿ)推导困惑

首先贴出你提到的检测代码（修正原代码中笔误的变量名）：

prime(x): i =2; while i < x { if x mod i == 0 { return 0 } i++ } return 1

问题1：x对应10ⁿ量级的推导逻辑 #

这里的n指的是输入值x的十进制位数，而非x本身的数值，推导前提为无前置零的n位十进制数，取值范围天然满足：

10^{n-1} ≤ x < 10^{n}
大O表示法描述的是算法复杂度的上界，且会忽略所有常数系数，因此10^{n-1}和10n属于同一个量级，直接取上界10ⁿ作为x的量级估计即可。
你举的x=17（2位十进制数）的例子中，实际循环仅需执行15次，但复杂度分析取的是同长度输入的最坏情况：2位十进制数中最大的素数是97，此时循环需要执行95次，已经非常接近10²=100，因此用10ⁿ作为同长度输入的循环次数上界是完全合理的。

问题2：n²项的推导逻辑 #

朴素素性检测的总耗时由两部分相乘得到：循环执行次数、单次循环内的运算耗时：

• 循环次数的上界已经通过输入长度推导得到，为O(10ⁿ)
• 单次循环内的核心运算是x mod i取余运算，朴素取余和小学阶段的逐位试除除法复杂度一致：m位数除以n位数的朴素除法时间复杂度为O(mn)，本次场景中被除数x是固定的n位十进制数，除数i最大可到x本身（同样为n位十进制数），因此单次取余运算的最坏时间复杂度为O(n*n)=O(n²)
  两部分复杂度相乘后，最终整体时间复杂度就是O(n²10ⁿ)。

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