producto máximo de primos entre sí factores de

Question

I esencialmente tiene un problema que se reduce a lo siguiente: Teniendo en cuenta algunos número (entero) n, encontrar un conjunto de números coprimos, decir c = (c , c ,. .., c _k), cada uno de menos de n, que satisfacen:

1) el producto de todos c _i es máxima.

2) La suma de todos los c _i es igual a n.

Esto puede terminar siendo una pregunta para MathOverflow, pero ¿hay algún tipo de algoritmo de fuerza no bruta para hacer esto?

Answer 1

Básicamente está buscando el mínimo múltiplo mínimo común de cualquier partición de n. El producto se conoce como función de Landau (ver OEIS A000793). Esto se puede calcular usando programación dinámica, vea here.