题解 | #分解质因数#

启发式试除法 (Heuristic Trial Division)

针对 的范围，采用基础试除法结合动态边界缩减是最优的工程选择。

1. 因子性质： 我们从最小的质数 开始尝试整除。如果 能被 整除，则 必然是一个质因子。这是因为，如果在遇到 之前，所有小于 的因子已经被除尽，那么 就不可能是一个合数（否则它的更小因子早已在前面被处理掉了）。
2. 动态缩减搜索空间： 每当发现一个因子 ，通过循环 n /= i 将其彻底除尽。这样做不仅能提取重复的质因子，还能快速收缩 的规模，从而降低后续的平方根边界。
3. 循环终止条件： 迭代至 即 。若循环结束后 ，说明剩余的 是一个大于原 边界的质数。

为什么不选择 Pollard's rho 算法？

Pollard's rho 算法在处理 时具有显著优势（复杂度约为 ），但其实现复杂且涉及大数取模运算。对于 级别，试除法在 次迭代内即可完成，执行时间通常在毫秒级，具有更高的可维护性和更低的常数开销。