如何加速寻找可被前n个三角数整除的首个符合条件数?
三角数公倍数查找的性能优化问题
我正在解决一道编程题,目标是先生成前n个三角数,再找出能被所有这些三角数整除的数,最终计算前m个符合条件的数的总和。
我的代码如下:
def checker(k,lst): for num in lst: if k%num == 0: pass if k%num != 0: return return True def sum_mult_triangnum(n, m): # 创建存储结果的列表 fin = [] # 生成前n个三角数的列表 lst = [n* (n+1) / 2 for n in range(1,n+1)] # 从最大的三角数开始查找符合条件的数 k = lst[-1] while True: if checker(k,lst) == True: fin.append(k) break else: k = k + lst[-1] # 生成后续m-1个符合条件的数 for i in range(m-1): fin.append(fin[-1] + fin[0]) # 计算总和 sum_of_multiples = sum(fin) return sum_of_multiples
示例:
n = 5 m = 8 sum_mult_triangnum(n, m) = 1080 三角数列表 = [1, 3, 6, 10, 15] 符合条件的数列表 = [30, 60, 90, 120, 150, 180, 210, 240]
观察示例可知,找到第一个符合条件的数后,后续的数可以通过公式快速生成:下一个数 = 前一个数 + 第一个符合条件的数。
目前我的代码通过暴力枚举从最大的三角数开始逐个查找首个符合条件的数,结果正确但耗时较长,请问有没有办法加速这一查找过程?
内容的提问来源于stack exchange,提问作者Fyker
相关产品推荐
相关产品推荐

