Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

A collection of positive integers d_1 d_2 ... d_k is a factorisation of a positive integer n if

d_1 * d_2 * ... * d_k = n

Each positive integer has a unique prime factorisation, but in general they also have factorisations in which some of the terms are composite. E.g.

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

Write a program, function, verb, or similar which takes as input a single positive integer and returns or prints a complete list of its distinct factorisations. The factorisations may be produced in any order, and their terms may be in any order, but no two should be permutations of each other. Factorisations may not include 1 with two exceptions: for input n you may give the factorisation n*1 instead of n; and for input 1 you may give the factorisation 1 instead of the empty list.

You may assume that the input will be in the range of a signed 32-bit integer. If the output is as a string, there should be a clear distinction between the delimitation of numbers within a factorisation and the delimitation of the factorisations, but it is not necessary (for example) for the factors to be joined with an *.

Your code should be capable of handling any valid input within 10 minutes on a reasonable desktop machine.

Examples

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
share|improve this question
    
Can you post the list of factorisations of 901800900 and 1338557220 somewhere where we can check them? My code is giving me 2048 and 1024 factorizations for those numbers, respectively, and I'm not sure why. – Sherlock9 14 hours ago
    
@Sherlock9, will do that when I get home. What I can do with an online generator is to give you a valid output for 5336100. – Peter Taylor 13 hours ago
3  
This reminds me of a ProjectEuler challenge (unfortunately I don't remember which). But there you had to count the number of factorizations instead of listing them. – flawr 10 hours ago
    
Related OEIS: A001055 – Sherlock9 3 hours ago

Haskell, 56 bytes

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

(2!)(1338557220::Int) prints in five minutes on my laptop, when compiled with ghc -O3.

Haskell, 62 bytes, but much faster

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) prints in a quarter of a second on my laptop, when compiled with ghc -O3.

share|improve this answer
    
How do I test this? ghc gives me Parse error: naked expression at top level and ghci gives me parse error on input `=' – Peter Taylor 9 hours ago
    
@PeterTaylor Replace the function (2!) with the program main = print ((2!) (1338557220::Int)), compile with ghc -O3 factor.hs, and run with ./factor. – Anders Kaseorg 3 hours ago

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)

Try it online

Runs in twenty seconds for 1338557220 on my laptop.

share|improve this answer
    
@PeterTaylor The usual way: pyth factor.pyth (or pyth -c 'Msam+Ldgd/Hdf!%HT>S@H2tG]]Hg2'), providing 16 on stdin. Make sure you are using a current version of Pyth; implicit Q was added in March. I can’t imagine how you might be getting division by zero, though. – Anders Kaseorg 3 hours ago
    
Arrrrgh. I was using " instead of ', and bash was expanding the !% to something else. – Peter Taylor 2 hours ago

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)}

Only borrowed @AndersKaseorg's square root trick because it ended up saving me bytes overall. Prints 1 for an input of 1, otherwise doesn't print 1s.

share|improve this answer

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

This is largely based on Anders Kaseorg's Pyth answer. Any golfing suggestions welcome.

import math
g=lambda n,m=2:[[n]]+[[d]+j for d in range(m,int(math.sqrt(n))+1)if n%d<1for j in g(n/d,d)]
share|improve this answer

Jelly, 15 bytes

ÆfŒ!ŒṖ€;/×/€Ṣ€Q

Try it online!

ÆfŒ!ŒṖ€;/×/€Ṣ€Q   Main monadic chain; argument: z
                  temp ← z
Æf                temp ← prime factors of temp (the array of primes whose product is temp)
  Œ!              temp ← all permutations of temp
    ŒṖ€           temp ← unique partitions for each array in temp
       ;/         temp ← eh, kind of flatten
         ×/€      temp ← for each partition in temp, product of each group
            Ṣ€    temp ← sorted each in temp
              Q   temp ← unique items in temp
share|improve this answer
    
Could you please provide a hexdump so that I can test this? – Peter Taylor 17 hours ago
    
@PeterTaylor eh, code page – Leaky Nun 17 hours ago
2  
I'm sure it would take much less time in total for you to run your file through xxd and then for me to do the same than for me to look up 15 chars in a large table and manually construct the hexdump. – Peter Taylor 16 hours ago
    
@PeterTaylor I don't have the file. – Leaky Nun 16 hours ago
1  
@PeterTaylor Jelly takes input as command-line arguments by default. jelly fn foo.jelly 16 works as intended. – Dennis 8 hours ago

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.