Una colección de enteros positivos d_1 d_2 ... d_kes una factorización de un entero positivo nsi

d_1 * d_2 * ... * d_k = n

Cada número entero positivo tiene una factorización prima única , pero en general también tienen factorizaciones en las que algunos de los términos son compuestos. P.ej

12 = 6 * 2 = 4 * 3 = 3 * 2 * 2

Escriba un programa, función, verbo o similar que tome como entrada un solo entero positivo y devuelva o imprima una lista completa de sus factorizaciones distintas. Las factorizaciones pueden producirse en cualquier orden, y sus términos pueden estar en cualquier orden, pero no deben existir permutaciones entre sí. Las factorizaciones pueden no incluir 1con dos excepciones: para la entrada n, puede dar la factorización en n*1lugar de n; y para la entrada 1puede dar la factorización en 1lugar de la lista vacía.

Puede suponer que la entrada estará en el rango de un entero de 32 bits con signo. Si la salida es como una cadena, debe haber una distinción clara entre la delimitación de números dentro de una factorización y la delimitación de las factorizaciones, pero no es necesario (por ejemplo) que los factores se unan con un *.

Su código debe ser capaz de manejar cualquier entrada válida dentro de los 10 minutos en una máquina de escritorio razonable.

Ejemplos

1                  [[]]
                or [[1]]
                or [[1 1]]

7                  [[7]]
                or [[7 1]]
                or [[1 7]]

12                 [[12] [6 2] [4 3] [2 3 2]]
                or variants

16                 [[2 2 2 2] [2 2 4] [2 8] [4 4] [16]]
                or variants

901800900          a list of 198091 factorisations

1338557220         a list of 246218 factorisations

Haskell, 56 bytes

_!1=[[]]
i!n=[j:f|j<-[i..n],mod n j<1,f<-j!div n j]
(2!)

(2!)(1338557220::Int)imprime en cinco minutos en mi computadora portátil, cuando se compila ghc -O3.

Haskell, 62 bytes, pero mucho más rápido.

i!n|i*i>n=[[n]]|0<1=[i:f|mod n i<1,f<-i!div n i]++(i+1)!n
(2!)

(2!)(1338557220::Int)imprime en un cuarto de segundo en mi computadora portátil, cuando se compila ghc -O3.

Pyth, 29 bytes

Msam+Ldgd/Hdf!%HT>S@H2tG]]Hg2

M                                def g(G, H):
                   @H2             square root of H
                  S                1-indexed range up to floor
                 >    tG           all but first G − 1 elements
            f                      filter for elements T such that:
              %HT                    H mod T
             !                       is false (0)
   m                               map for elements d:
       gd/Hd                         g(d, H/d)
    +Ld                              prepend d to each element
  a                     ]]H        append [[H]]
 s                                 concatenate
                           g2Q   print g(2, input)

Pruébalo en línea

Se ejecuta en veinte segundos 1338557220en mi computadora portátil.

Python , 252 313 312 311 145 141 137 135 103 84 83 bytes

Esto se basa en gran medida en la respuesta Pyth de Anders Kaseorg . Cualquier sugerencia de golf bienvenida. Pruébalo en línea!

Editar: 19 bytes de golf gracias a Dennis. Se corrigió un error tipográfico en el código y se agregó un enlace TIO.

g=lambda n,m=2:[[n]]+[j+[d]for d in range(m,int(n**.5)+1)if n%d<1for j in g(n/d,d)]

Sin golf:

def g(n, m=2):
    a = [[n]]
    s = int(n**.5) + 1
    for d in range(m, s):
        if n%d == 0:
            for j in g(n/d, d):
                a.append([d]+j)
    return a

JavaScript (ES6), 83 bytes

f=(n,a=[],m=2,i=m)=>{for(;i*i<=n;i++)n%i<1&&f(n/i,[...a,i],i);console.log(...a,n)}

Solo tomé prestado el truco de raíz cuadrada de @ AndersKaseorg porque terminó ahorrándome bytes en general. Imprime 1una entrada de 1, de lo contrario no imprime 1s.

Ruby 1.9+, 87 89 87 bytes

Esta respuesta se basa en la respuesta Pyth de Anders Kaseorg . Este código solo funciona para versiones posteriores a Ruby 1.9, ya que las lambdas stabby ->solo se introdujeron en 1.9. Cualquier sugerencia de golf es bienvenida.

g=->n,m=2{(m..Math.sqrt(n)).select{|i|n%i<1}.flat_map{|d|g[n/d,d].map{|j|[d]+j}}+[[n]]}

Sin golf:

def g(n, m=2)
  a = [[n]]
  s = (m..Math.sqrt(n))
  t = s.select{|i|n%i<1}
  t.each do |d|
    g[n/d,d].each do |j|
      a.push([d]+j)
    end
  end
  return a
end

J, 52 bytes

[:~.q:<@/:~@(*//.)"$~#@q:_&(;@]<@(,~"{~0,#\@~.)"1)}:

No es tan eficiente como podría ser, ya que algunas factorizaciones pueden repetirse y se debe hacer un pase final después de clasificar cada factorización y luego desduplicar.

Pruébalo en línea! (Pero trate de mantener los valores de entrada pequeños).

En mi escritorio, los tiempos son

   f =: [:~.q:<@/:~@(*//.)"$~#@q:_&(;@]<@(,~"{~0,#\@~.)"1)}:
   timex 'r =: f 1338557220'
3.14172
   # r
246218
   timex 'r =: f 901800900'
16.3849
   # r
198091

Explicación

Este método se basa en generar todas las particiones establecidas para los factores primos del entero de entrada n . El rendimiento es mejor cuando n no tiene cuadrados, de lo contrario se crearán factorizaciones duplicadas.

[:~.q:<@/:~@(*//.)"$~#@q:_&(;@]<@(,~"{~0,#\@~.)"1)}:  Input: integer n
                                                  }:  Curtail, forms an empty array
                       q:                             Prime factorization
                     #@                               Length, C = count prime factors
                         _&(                     )    Repeat that many times on x = []
                                 (            )"1       For each row
                                            ~.            Unique
                                         #\@              Enumerate starting at 1
                                       0,                 Prepend 0
                                  ,~"{~                   Append each of those to a
                                                          copy of the row
                               <@                         Box it
                            ;&]                         Set x as the raze of those boxes
                                                      These are now the restricted growth
                                                      strings of order C
    q:                                                Prime factorization
            (    )"$~                                 For each RGS
               /.                                       Partition it
             */                                         Get the product of each block
        /:~@                                            Sort it
      <@                                                Box it
[:~.                                                  Deduplicate