互質的最大產品因素

Question

我基本上具有歸結於以下一個問題：給定一些（整數）數n，找到一組互質數，例如c =（C ，C 。 ..，C _ķ），每個小於n，滿足：

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

2）全部的總和c _i等於n。

這可能會成爲MathOverflow的一個問題，但是有沒有一種非蠻力算法可以做到這一點？

Answer 1

你基本上是在尋找n的任何分區的最大最小公倍數。該產品被稱爲Landau的功能（參見OEIS A000793）。這可以使用動態編程進行計算，請參見here。