大数字除数个数计算出现运行时错误 现有方法运行缓慢求优化

计算大数字除数个数效率低/报错的原因 #

• 绝大多数低效实现都采用了暴力遍历逻辑：从1遍历到目标数n或n/2逐一判断是否为除数，时间复杂度为O(n)，数值超过1e6后耗时就会明显上升，数值达到1e12以上时基本不可能在合理时间内跑完，同时如果代码没有适配大整数类型，还会触发整型溢出类运行时错误。
• 未利用除数计数的数学性质：若对n做质因数分解可得n = p₁^a₁ * p₂^a₂ * ... * p_k^a_k（p为质因子，a为对应指数），则n的总除数个数为(a₁+1)*(a₂+1)*...*(a_k+1)，暴力实现完全没有用到该性质，做了大量无效运算。
• 遍历边界不合理：即使做了简化遍历到sqrt(n)的优化，很多实现也没有处理完全平方数的特殊场景，或者没有提前过滤偶数因子，额外增加了循环次数。

高效实现方案 #

1. 普通试除法（适用1e12以内的数值） #

算法逻辑如下：

• 初始化计数结果为1
• 先统计质因子2的指数，将计数乘以（指数+1），同时把n中所有2的因子除尽
• 从3开始遍历到sqrt(n)，步长设为2（仅遍历奇数），每找到一个质因子就统计其对应指数，将计数乘以（指数+1），同时把n中该质因子的所有项除尽
• 遍历结束后如果剩余的n大于1，说明剩余值本身是一个质因子，将计数乘以2即可
• 全程使用大整数类型存储数值和结果，避免溢出

Python示例代码：

def count_divisors(n):
    if n == 0:
        return 0
    count = 1
    # 处理质因子2
    exponent = 0
    while n % 2 == 0:
        exponent += 1
        n = n // 2
    count *= (exponent + 1)
    # 处理奇数质因子
    i = 3
    while i * i <= n:
        exponent = 0
        while n % i == 0:
            exponent += 1
            n = n // i
        count *= (exponent + 1)
        i += 2
    # 剩余的质因子
    if n > 1:
        count *= 2
    return count

2. Pollard's Rho算法优化（适用1e18以上的超大数值） #

如果需要处理1e18以上的超大整数，普通试除法效率不足，可以使用Pollard's Rho随机化质因数分解算法，结合Miller-Rabin素性测试，可将质因数分解的时间复杂度降到近似O(n^(1/4))，大幅提升超大数的计算效率。

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