Encontrar todas las maneras para descomponer un número en

Question

Un ejemplo de lo que estoy buscando probablemente explique la pregunta mejor. 24 puede ser escrita como:

• 12 · 2
• 6 · 2 · 2
• 3 · 2 · 2 · 2
• 8 · 3
• 4 · 2 · 3
• 6 · 4

Estoy familiarizado con la búsqueda de todos los factores primos de un número ($24 = 3 · 2^3$), así como todos los pares de factores (24 = 12·2, 8·3, 6·4). Estoy asumiendo que uno o ambos formarán la base de la respuesta, pero no puedo averiguar un algoritmo para encontrar todas las posibles formas de representar un número como un producto de 2 o más números. Así que, ¿qué es un (preferiblemente eficiente) de manera de lograr esto?

Nota: esta no es la tarea, es sólo para mi propio conocimiento.

Answer 1

Eso se llama particiones multiplicativas y hay una función generadora por Oppenheim y McMahon. Se podría utilizar. La lista del número de particiones multiplicativos está en http://oeis.org/A001055

Answer 2

Bueno si tienes la facturización primera de un número (vamos a usar tu ejemplo de 24), entonces cualquier combinación de sus factores primeros debe ser un factor. $$24 = 3\times 2^3$ $ Para cualquier combinación de {3, 2, 2, 2} es un factor. La manera que teniendo todos los subconjuntos de un conjunto de manera eficiente es más un problema del CS.

Pero solo para el punto de Inicio:

{{3} = 2 {3, 2} = 6, {3,2,2} = 12, {3,2,2,2} = 24, {2} = 2, {2, 2} = 4 {2,2,2} = 8}

Y luego recordar 1.