Perfect Power算法循环迭代次数过多无法运行优化求助

原有代码问题分析 #

现有代码采用双层O(n)循环，时间复杂度为O(n²)，当n值超过100时迭代次数就会指数级膨胀，且m**k运算会生成极大值占用内存，完全无法处理稍大的n值。

核心优化思路 #

• 缩小指数k的取值范围：由于最小的底数m为2，因此k的最大可能值为log₂n（满足2^k ≤n），无需遍历到n，比如n=10^6时k的上限仅为20
• 替换m的循环为根运算验证：对每个合法的k，直接计算n的k次算术根，仅验证根附近的1-2个整数值是否满足m**k =n即可，完全消除m的循环
• 幂运算提前终止：验证时若幂运算结果超过n就直接停止计算，避免无效运算

优化后Python实现代码 #

import math

def isPP(n):
    # k的最大取值为log2(n)，向下取整后加1避免边界误差
    max_k = int(math.log2(n)) + 1
    for k in range(2, max_k + 1):
        # 计算n的k次根，取整
        m = round(n ** (1.0 / k))
        # 验证m-1、m、m+1避免浮点精度误差
        for candidate in [m-1, m, m+1]:
            if candidate <= 1:
                continue
            if candidate ** k == n:
                return (candidate, k)
    return None

优化效果说明 #

优化后时间复杂度仅为O(log₂n)，哪怕n是10^18量级，log2(n)也只有60左右，迭代次数不到60次，完全不会出现运行卡顿或者内存溢出问题。对浮点精度的容错处理也保证了不会因为根计算的精度问题漏判合法解。

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