求n以内多重完全数的高效算法（原O(n²)算法需优化）

原算法核心问题 #

你当前的算法采用两层嵌套循环逐个计算每个数的约数和，时间复杂度为O(n²)，当n较大时（比如n>1000），运行效率会急剧下降——核心问题在于重复计算约数，每个数都要遍历1到X来寻找约数，完全没有利用约数的分布规律。

优化思路 #

1. 筛法预处理约数和数组

借鉴埃拉托斯特尼筛法的思路，反向遍历计算每个数的约数和：

• 初始化一个长度为n+1的数组sum_div，所有元素初始为0
• 遍历每个数i从1到n，将i加到它所有倍数的约数和中（因为i是这些倍数的约数）
• 这样只需O(n log n)的时间就能完成所有数的约数和计算，比原算法的O(n²)效率提升几个数量级

2. 简化判断逻辑

原算法的两次判断可以合并为一次：检查约数和sum_div[X]是否是X的1~11倍，即sum_div[X] % X == 0且1 <= sum_div[X] // X <= 11，这样代码更简洁高效。

优化后的代码 #

def find_multiply_perfect_numbers(n):
    # 初始化约数和数组，sum_div[X]表示X的所有约数之和
    sum_div = [0] * (n + 1)
    for i in range(1, n + 1):
        # 遍历i的所有倍数，将i作为约数加到倍数的约数和中
        for j in range(i, n + 1, i):
            sum_div[j] += i
    
    result = []
    for x in range(1, n + 1):
        quotient = sum_div[x] // x
        # 检查约数和是否是x的1~11倍（注意sum_div[x]必须能被x整除）
        if sum_div[x] % x == 0 and 1 <= quotient <= 11:
            result.append(x)
    return result

额外优化点（可选） #

• 如果n极大（比如n>1e6），可以考虑使用**线性筛（欧拉筛）**进一步优化约数和的计算，时间复杂度降到O(n)，但实现稍复杂，对于大多数场景，上面的筛法已经足够高效。
• 可以提前终止一些不必要的计算，比如当sum_div[x]已经超过11*x时，后续无需再累加，但实际收益有限，代码复杂度会上升。

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