回复: 把整数分解为质数和 找到一个极快的方法,假设X(n) = n的质数分解。
1.计算质数序列P(i)
2.计算和序列S(i) = P(1) + P(2) + ... + P(n)
3.在S(i)里面找到大于等于整数n的最小数,记为S(k)
4.用DP/整数背包/...求S(k) - n的质数分解。
5.如果存在,或者S(k) - n == 0,那么结果就是 { P(1), P(2), ..., P(k) } - X(n)
6.如果不存在,k += 1, go to 4
另外,第4步可以递归地调用这个方法来求出S(k) - n的分解。这个算法不是很完善,不过意思应该到了。
btw:我是在看另一断程序的时候受到的启发,虽然那段程序不完全是这样做的。 |