Maximum product of coprime factors

Question

I essentially have a problem which boils down to the following: Given some (integer) number n, find a set of coprime numbers, say c = (c₁, c₂, ..., c_k), each less than n, which satisfy:

1) The product of all c_i is maximal.

2) The sum of all c_i is equal to n.

This may end up being a question for MathOverflow, but is there any kind of non-brute force algorithm for doing this?

Answer 1

You're basically looking for the maximal least common multiple of any partition of n. The product is known as Landau's function (see OEIS A000793). This can be computed using dynamic programming, see here.