如何用for/while循环求因子唯一倍数和？代码超时问题求助

给定因子列表（multiples）和上限（limit），计算所有小于上限的该因子列表的唯一倍数之和，所有输入均大于等于0。

示例 #

当上限为20，因子列表为[3,5]时：

• 小于20的3的倍数：3、6、9、12、15、18
• 小于20的5的倍数：5、10、15
• 唯一倍数集合：{3,5,6,9,10,12,15,18}
• 求和结果：78

我编写了三段Python代码实现该功能，但测试时均提示your tests timed out（测试超时），疑似存在无限循环或性能问题；其中使用if语句的版本还存在结果错误的问题，现寻求问题原因及解决方案。

代码1 #

def sum_of_multiples(limit, multiples):

    n = 1
    sum_m = []

    for i in multiples:
        while i*n < limit: 
            sum_m.append(i*n)
            n+=1
            if i*n > limit:
                break
                
    return sum(sum_m)

代码2 #

def sum_of_multiples(limit, multiples):

    n = 1
    sum_m = []

    for i in multiples:
        while i*n < limit: 
            sum_m.append(i*n)
            n+=1
        else:
            break
                
    return sum(sum_m)

代码3 #

def sum_of_multiples(limit, multiples):

    n = 1
    sum_m = []

    for i in multiples:
        if i*n < limit: 
            sum_m.append(i*n)
            n+=1
                
    return sum(sum_m)

代码问题拆解 #

代码1 & 代码2：超时/逻辑失效 #

• 核心问题：变量n全局只初始化一次，处理第一个因子时持续递增，后续因子复用这个已经变大的n，要么直接跳过循环，要么遇到因子为1这类情况时，n会持续递增到接近limit，引发超长循环导致超时。另外代码2中的else: break会让程序处理完第一个因子就终止整个循环，完全忽略后续因子。
• 额外问题：未做去重处理，重复倍数会被多次累加，导致结果错误。

代码3：结果错误 #

• 核心问题：每个因子仅处理一次倍数（n逐次+1），比如因子3只加入31=3，因子5只加入52=10，完全没有遍历该因子的所有倍数，逻辑完全不符合需求。

正确实现方案 #

方案1：集合去重法（直观易读） #

通过集合自动去重，遍历每个因子生成所有小于limit的倍数：

def sum_of_multiples(limit, multiples):
    unique_multiples = set()
    # 过滤0因子，避免无限循环
    valid_factors = [m for m in multiples if m != 0]
    for m in valid_factors:
        current = m
        while current < limit:
            unique_multiples.add(current)
            current += m
    return sum(unique_multiples)

方案2：数学公式法（性能最优，适配超大limit） #

利用容斥原理计算，避免遍历所有倍数，适合limit极大的场景：

def sum_of_multiples(limit, multiples):
    from math import gcd
    from itertools import combinations

    # 计算两个数的最小公倍数
    def lcm(a, b):
        return a * b // gcd(a, b)
    
    # 计算多个数的最小公倍数
    def lcm_multiple(numbers):
        result = 1
        for num in numbers:
            result = lcm(result, num)
        return result
    
    # 过滤无效因子（0或大于等于limit的因子）
    valid_factors = [m for m in multiples if m != 0 and m < limit]
    if not valid_factors:
        return 0
    
    total = 0
    # 容斥原理：加单个因子的和，减两两LCM的和，加三三LCM的和...
    for k in range(1, len(valid_factors)+1):
        for combo in combinations(valid_factors, k):
            current_lcm = lcm_multiple(combo)
            if current_lcm >= limit:
                continue
            # 计算该LCM的倍数之和
            count = (limit - 1) // current_lcm
            sum_combo = current_lcm * count * (count + 1) // 2
            # 根据组合长度奇偶性加减
            total += sum_combo if k % 2 == 1 else -sum_combo
    return total

测试验证 #

用示例输入测试两种方案：

print(sum_of_multiples(20, [3,5]))  # 输出78，符合预期

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