如何优化Codewars Buddy Pairs题Python解法 解决执行超时问题

题目链接：https://www.codewars.com/kata/59ccf051dcc4050f7800008f/shell

Buddy pairs（伙伴数对）：正整数n的真因数指排除n本身以外的所有因数，本文中除数均指代真因数，例如100的真因数为1、2、4、5、10、20、25、50。
定义s(n)为n的所有真因数之和，若两个正整数满足彼此的真因数和等于对方加1，则称二者为Buddy pairs，即：若s(m) = n + 1且s(n) = m + 1，则(n, m)为伙伴数对。
示例：48与75是符合要求的数对：48的真因数和为76 = 75 + 1，75的真因数和为49 = 48 + 1。
任务要求：给定两个正整数start、limit，实现函数buddy(start, limit)，返回首个满足要求的伙伴数对(n, m)：n处于[start, limit]闭区间内，m > n且可大于limit；若无符合要求的数对则返回"Nothing"。

测试用例1：test.assert_equals(buddy(10, 50), [48, 75])
测试用例2：test.assert_equals(buddy(2177, 4357), "Nothing")
测试用例3：test.assert_equals(buddy(57345, 90061), [62744, 75495])
测试用例4：test.assert_equals(buddy(1071625, 1103735), [1081184, 1331967])

原有超时代码：

def sum_divisors(num):
    sum = 0
    for i in range(1, num):
        if num % i == 0:
            sum += i

    return sum


def buddy(start, limit):
    for i in range(start, limit + 1):
        sum = sum_divisors(i)
        sum_minus_one = sum_divisors(sum - 1)

        if start > sum - 1:
            continue

        if i == (sum_minus_one - 1):
            return [i, sum - 1]

    return "Nothing"

优化思路 #

• 优化真因数求和逻辑：原有sum_divisors遍历范围是1到num-1，时间复杂度为O(n)，大数场景下性能极差。实际上因数是成对出现的，只需要遍历到sqrt(num)即可，遇到可整除的数直接把成对的另一个因数也加进来，注意排除等于num本身的情况，以及完全平方数不要重复加平方根，优化后时间复杂度降到O(√n)。
• 调整判断顺序减少冗余计算：原有代码先计算sum_minus_one再做合法性判断，优化后先判断m=s(n)-1是否满足m>n的要求，不满足直接跳过，不需要再计算m的真因数和，能砍掉大量无效计算。
• 移除无效判断：原有代码中start>sum-1的判断完全多余，因为要求m>n且n>=start，m自然大于start，该判断可以直接删除。

优化后可通过测试代码 #

import math

def sum_divisors(num):
    if num < 2:
        return 0
    total = 1
    sqrt_num = int(math.sqrt(num))
    for i in range(2, sqrt_num + 1):
        if num % i == 0:
            total += i
            other = num // i
            if other != i:
                total += other
    return total

def buddy(start, limit):
    for n in range(start, limit + 1):
        s_n = sum_divisors(n)
        m = s_n - 1
        if m <= n:
            continue
        s_m = sum_divisors(m)
        if s_m == n + 1:
            return [n, m]
    return "Nothing"

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