如何将一个整数分解为另外两个整数

Question

我需要分解一个形式为n = ab(a+b)的给定整数。由于b可以至少为1，我们约束a上升到ceil(sqrt(n)).。通过两个变量的对称性，我们发现b可以上升到ceil(sqrt(n/(2*a))).。我使用的代码如下。当我提供n=30=2*3*(2+3)或其他一些例子时，它提供了正确的答案。当我提供9510432 = 1256*6*(1256+6)时，它提供的是错误的(0,0)。当我提供一个15位或更长的数字时，速度太慢了。你能帮我理解这一点吗，即为什么它有时是错误的，有时是正确的？如何使它在时间复杂性方面更高效？我最终尝试使用itertools中的组合来获得元组列表，但没有成功地正确实现它。

import math as m
from itertools import combinations
def decompose(n):
a = 0
b = 0
for i in range(1, m.ceil(m.sqrt(n))+1):
for j in range(i, m.ceil(m.sqrt(n/(2*i)))+1):
if n == i*j*(i+j):
a = i
b = j
break
return a, b  
print(decompose(9510432))

Answer 1

您的范围错了——您放了i而不是1。试试这个：

替换：

for j in range(i, m.ceil(m.sqrt(n/(2*i)))+1):

带有：

for j in range(1, m.ceil(m.sqrt(n/(2*i)))+1):