自研O(n*log(log(n)))整数分解算法的性能排名与定位咨询

1. 算法本质与复杂度确认 #

你的compute_prime_factors函数本质是埃拉托斯特尼筛法的变种，通过维护数组记录每个数的质因数集合，最终提取目标数n的质因数列表：

• 时间复杂度：确实为O(n log log n)，和标准埃氏筛的时间复杂度一致
• 空间复杂度：O(n)，需要创建长度为n+1的数组存储所有数的质因数信息

2. 与主流整数分解算法的核心对比 #

整数分解算法的性能不能仅看渐近复杂度的字面类型，核心要看输入规模的适用场景，以下是关键对比结论：

• 对比试除法：试除法时间复杂度为O(√n)，空间复杂度为O(1)。当n较小时（比如n < 1e6），两者性能接近，但你的算法需要额外分配O(n)空间，小数据场景下空间开销反而更大；当n超过1e8时，O(n)的内存占用会达到GB级，完全无法实用，而试除法仍能以常数空间运行。
• 对比Pollard's Rho算法：这是工程中目前最常用的高效分解算法，平均时间复杂度为O(n^(1/4))，空间复杂度仅为O(log n)。对于中等规模整数（比如1e12到1e20），Pollard's Rho可以在毫秒级完成分解，而你的算法在n=1e12时，O(n log log n)的时间开销完全不可执行。
• 对比GNFS（普通数域筛法）：你提到GNFS是亚指数时间复杂度，但要明确：整数分解问题的输入规模是n的二进制位数（即log₂n），你的算法的时间复杂度从输入规模角度看是指数级（O(2^k log k)，k为n的位数），而GNFS的亚指数复杂度（O(e^((c + o(1))(log n)^(1/3)(log log n)^(2/3)))）在处理100位以上的大数时，速度远远超过你的算法——这类大数场景下，你的算法甚至无法启动（内存和时间都不足以支撑）。

3. 最终定位结论 #

你的算法属于基于筛法的预处理型分解算法，仅能适用于极小整数（n ≤ 1e6左右）的分解场景，完全无法优于当前主流的整数分解算法（Pollard's Rho、GNFS等）。它的核心思路是埃氏筛的扩展，没有突破现有筛法的性能瓶颈，对于大数分解来说，时间和空间开销都不具备可行性。

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