有什么有用的数学函数/算法可以分解大数字吗

Question

所以我想做的是把成千上万的数字分解成更小的数字，最好是2~9。

我想到的第一件事是素数分解，例如，数字49392可以表示为(2x2x2x3x3x7x7x7(。但也有素数和25378=2×12689这样的数字不能只用乘法来表示。

所以我想用乘法和加法来分解这些数字，例如，数字25378可以表示为25346+32=(2×19×23×29(+(2^5(。尽管如此，23和29太大了，但我只是选择了随机数，只是为了表明我的意思，用加法和乘法来表示大数字，我相信有比25346和32更好的数字组合来表示25378。

无论如何，我认为编程这将涉及大量不必要的if语句，并且从全局来看会非常缓慢。所以我想知道，是否有一个数学算法或函数可以做这件事？如果没有，我可以自己优化代码，但我只是好奇，尽管我自己在谷歌上找不到任何东西。

Answer 1

假设问题是将一个数字写为包含数字1-9、加法和乘法(最简单=运算符数量最少(的最简单表达式，那么这个Python程序在O(N^2(时间内完成这一操作。

一个数字N可以写成两个较小数字的和或乘积，所以如果你预先计算了构造数字1.N-1的最简单方法，那么你可以在O(N(时间内找到构造N的最简单方式。那么，这只是一个避免重复工作的问题——例如，在不损失表达式a+B和AB、a<B、 并很好地打印出最后的表达式。

def nice_exp(x, pri):
if isinstance(x, int):
return str(x)
else:
oppri = 1 if x[0] == '*' else 0
if oppri < pri:
bracks = '()'
else:
bracks = ['', '']       
return '%s%s %s %s%s' % (bracks[0], nice_exp(x[1], oppri), x[0], nice_exp(x[2], oppri), bracks[1])
def solve(N):
infinity = 1e12
size = [infinity] * (N+1)
expr = [None] * (N+1)
for i in range(N+1):
if i < 10:
size[i] = 1
expr[i] = i
continue
for j in range(2, i):
if j * j > i: break
if i%j == 0 and size[j] + size[i//j] + 1 < size[i]:
size[i] = size[j] + size[i//j] + 1
expr[i] = ('*', expr[j], expr[i//j])
for j in range(1, i):
if j > i-j: break
if size[j] + size[i-j] + 1 < size[i]:
size[i] = size[j] + size[i-j] + 1
expr[i] = ('+', expr[j], expr[i-j])
return nice_exp(expr[N], 0)
print(solve(25378))

输出：

2 * (5 + 4 * 7 * (5 + 7 * 8 * 8))