数组元素约数和计算超时问题：求优化方案及算法思路

问题背景 #

需求是计算数组中每个数的所有约数之和并返回结果，示例输入[2,4,10]，输出[3,7,18]。但当前代码处理大数（如986815066、100000000）时会超时，原代码如下：

def maxSubsetSum(k):
    summedResult = []
    listOfNumbers = k
    i = 0
    while i < len(listOfNumbers):
        commonMultiples = []
        for each in range(1, listOfNumbers[i] + 1):
            if listOfNumbers[i] % each == 0:
                commonMultiples.append(each)
        summedResult.append(sum(commonMultiples))
        i += 1
    return summedResult

原代码问题分析 #

原代码对每个数都遍历从1到该数的所有整数，时间复杂度为O(n)（n为当前数的大小），遇到百万、千万级别的大数时，循环次数过多直接导致超时。

优化方法 #

方法1：利用约数对称性减少遍历次数 #

每个数的约数都是成对出现的（d和n/d），比如10的约数对是(1,10)、(2,5)。我们只需要遍历到sqrt(n)，找到每个约数d后，同时把d和n/d加入求和集合（注意当d == n/d时，只加一次，避免重复）。

伪代码思路

函数 calculate_divisor_sum(n):
    如果n == 0:
        返回0
    初始化sum_total为0
    初始化d从1到sqrt(n)的整数:
        如果n % d == 0:
            sum_total += d
            如果d != n/d:
                sum_total += n/d
    返回sum_total

函数 process_array(numbers):
    初始化结果列表result
    遍历numbers中的每个num:
        将calculate_divisor_sum(num)加入result
    返回result

方法2：质因数分解法（更适合超大数） #

根据数论中的约数和公式：若n的质因数分解为n = p₁^a₁ * p₂^a₂ * ... * p_k^a_k，则约数和为(1+p₁+p₁²+...+p₁^a₁) * (1+p₂+p₂²+...+p₂^a₂) * ... * (1+p_k+p_k²+...+p_k^a_k)。

伪代码思路

函数 calculate_divisor_sum(n):
    如果n == 1:
        返回1
    初始化sum_total为1
    当前质因数p从2开始:
        如果p*p > n:
            跳出循环
        如果n能被p整除:
            初始化当前项和term为1
            当n能被p整除时:
                term *= p
                sum_total *= (term + 1)  # 等价于累加1+p+p²+...+p^a
                n = n / p
    如果n > 1:  # 剩余的n是一个质数
        sum_total *= (1 + n)
    返回sum_total

函数 process_array(numbers):
    初始化结果列表result
    遍历numbers中的每个num:
        将calculate_divisor_sum(num)加入result
    返回result

优化后的Python代码示例 #

这里给出基于质因数分解的实现，处理大数效率极高：

def calculate_divisor_sum(n):
    if n == 1:
        return 1
    total = 1
    p = 2
    while p * p <= n:
        if n % p == 0:
            term = 1
            while n % p == 0:
                term *= p
                total *= (term + 1)
                n = n // p
        p += 1
    if n > 1:
        total *= (1 + n)
    return total

def maxSubsetSum(numbers):
    return [calculate_divisor_sum(num) for num in numbers]

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