algorithm - 互质因子的最大乘积

Question

我基本上有一个问题可以归结为以下问题:给定一些(整数)数 n，找到一组互质数，比如 c = (c₁, c₂, ..., c_k)，每一个都小于n，满足:

1) 所有c_i的乘积是最大的。

2) 所有c_i之和等于n。

这可能最终成为 MathOverflow 的一个问题，但是是否有任何一种非暴力算法可以做到这一点？

Answer 1

您基本上是在寻找 n 的任意分区的最大最小公倍数。该乘积称为 Landau 函数(请参阅 OEIS A000793)。这可以使用动态规划计算，参见 here .