互质的最大产品因素

Question

我基本上具有归结于以下一个问题：给定一些（整数）数n，找到一组互质数，例如c =（C ，C 。 ..，C _ķ），每个小于n，满足：

1）所有C的产物_我是最大的。

2）全部的总和c _i等于n。

这可能会成为MathOverflow的一个问题，但是有没有一种非蛮力算法可以做到这一点？

Answer 1

你基本上是在寻找n的任何分区的最大最小公倍数。该产品被称为Landau的功能（参见OEIS A000793）。这可以使用动态编程进行计算，请参见here。