Python代码优化求助：平方约数和为平方数的程序提速

首先，先明确问题需求：

给定两个整数m、n（1≤m≤n），找出m到n之间所有满足「平方约数和为完全平方数」的整数。结果为二维数组，每个子数组包含符合条件的整数及其平方约数和。例如：

• list_squared(1, 250) 返回 [[1, 1], [42, 2500], [246, 84100]]
• list_squared(42, 250) 返回 [[42, 2500], [246, 84100]]

原代码的性能瓶颈 #

你提供的原代码逻辑是对的，但运行慢的核心原因是约数计算的效率太低：

from math import sqrt
def list_squared(m, n):
    #sum of the squared divisors of a number
    def D(x):
        return sum([i**2 for i in range(1,x+1) if not x%i])
    #returns array of arrays containing each num and D(num) from m to n if D(num) is square
    return [[i,D(i)] for i in range(m,n) if sqrt(D(i)).is_integer()]

在D(x)函数中，你遍历了从1到x的所有数来寻找约数，当x很大时（比如接近1e5或更大），这个循环的时间复杂度是O(x)，会导致程序运行极慢。

优化方案 #

我们可以从两个核心点入手优化：

1. 高效计算约数的平方和

约数是成对出现的：如果i是x的约数，那么x//i也一定是x的约数。利用这个特性，我们只需要遍历到sqrt(x)即可，时间复杂度直接降到O(sqrt(x))，效率提升非常明显。

2. 更可靠的完全平方数判断

使用浮点数的is_integer()可能会有精度问题（比如很大的数开平方后浮点数精度丢失），更好的方式是计算整数平方根k，然后判断k*k是否等于平方和。

另外，我们可以用functools.lru_cache缓存已经计算过的结果，如果函数被多次调用，或者范围内有重复计算的情况，能进一步提升效率。

优化后的代码 #

from math import isqrt
from functools import lru_cache

def list_squared(m, n):
    @lru_cache(maxsize=None)
    def sum_squared_divisors(x):
        total = 0
        # 遍历到sqrt(x)，成对处理约数
        for i in range(1, isqrt(x) + 1):
            if x % i == 0:
                total += i*i
                counterpart = x // i
                if counterpart != i:
                    total += counterpart*counterpart
        return total
    
    result = []
    for num in range(m, n):
        s = sum_squared_divisors(num)
        k = isqrt(s)
        if k * k == s:
            result.append([num, s])
    return result

优化效果说明 #

• 约数计算的循环次数从x次减少到sqrt(x)次，比如x=1e6时，循环次数从1e6次降到1000次，效率提升1000倍。
• isqrt是Python 3.8+新增的整数平方根函数，返回的是整数，避免了浮点数精度问题。
• 缓存装饰器lru_cache会记住已经计算过的sum_squared_divisors(x)结果，如果同一个x被多次调用（比如函数重复执行时），直接返回缓存值，无需重复计算。

测试你的例子：

print(list_squared(1, 250))  # 输出 [[1, 1], [42, 2500], [246, 84100]]
print(list_squared(42, 250))  # 输出 [[42, 2500], [246, 84100]]

完全符合预期，而且运行速度会比原代码快很多，即使处理很大的n也能快速完成。

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