Composite Factorization

Question

This is similar to prime factorization, where you find the smallest prime factors of a number (i.e. 8 = 2 x 2 x 2). But this time, you are to return an array/list of the smallest composite factors of any given positive integer n. If n is prime, simply return an empty list.

Examples:

• Prime:

  n = 2
  Result: []
  

• Composite and Positive:

  n = 4
  Result: [4]
  
  n = 32
  Result: [4, 8]
  
  n = 64
  Result: [4, 4, 4]
  
  n = 96
  Result: [4, 4, 6]
  

Rules:

• The product of the factors in the list must equal the input

• Standard loopholes are banned

• An array/list must be returned or printed (i.e. [4])

• Your program must be able to return the same results for the same numbers seen in the examples above

• The factors in the array/list can be strings so [4] and ["4"] are both equally valid

• A prime number is any positive integer whose only possible factors are itself and 1. 4 returns [4] but is not prime since 2 is also a factor.

• A composite number for this challenge any positive integer that has 3 or more factors (including 1) like 4, whose factors are 1, 2, and 4.

Clarifications:

• Given a number such as 108, there are some possibilities such as [9, 12] or [4, 27]. The first integer is to be the smallest composite integer possible (excluding 1 unless mandatory) thus the array returned should be [4, 27] since 4 < 9.

• All factors after the first factor need to be as small as possible as well. Take the example of 96. Instead of simply [4, 24], 24 can still be factored down to 4 and 6 thus the solution is [4, 4, 6].

Winning Criteria:

Shortest code wins since this is code-golf.

Answer 1

Jelly, 12 bytes

»0Æf×Ṫ$-¦×2/

Try it online!

How it works

»0Æf×Ṫ$-¦×2/  Main link. Argument: n

»0            Take the maximum of n and 0.
              Jelly's prime factorization does weird things for negative numbers.
  Æf          Take the prime factorization of the maximum.
        ¦     Conditional application:
    ×Ṫ$         Pop the last element of the array and and multiply all elements
                of the remaining array with it.
       -        Replace the element at index -1 with the corresponding element in
                the result.
              This effectively multiplies the last two elements of the array.
         ×2/  Multiply the factors in non-overlapping pairs. If the last element
              does not have a partner, leave it unmodified.

Answer 2

05AB1E, 8 bytes

Òā¨ÉÅ¡P¦

Try it online!

Explanation:

            # implicit input (example: 72)
Ò           # prime factorization ([2, 2, 2, 3, 3])
 ā          # indices ([1, 2, 3, 4, 5])
  ¨         # drop the last element ([1, 2, 3, 4])
   É        # is odd ([1, 0, 1, 0])
    Å¡      # split on 1s ([[], [2, 2], [2, 3, 3]])
      P     # product ([1, 4, 18])
       ¦    # drop the first element ([4, 18])
            # implicit output

Note that this correctly returns [] for prime inputs.

Answer 3

Haskell 150

Pretty basic answer but:

r n=p n$n-1
p 1 _=[]
p n 1=[n]
p n m
 |n`mod`m==0=p(n`div`m)(m-1)++r m
 |1>0=p n$m-1
i[x,y,z]=[x*y*z]
i(x:y:z)=x*y:i z
i _=[]
c n
 |n>0=i.r$n
 |1>0=[]

Works very straightforwardly: find all the prime factors of the input (the p function) in a way that produces them sorted ascending, and multiply them by twos (with the exception of multiplying three together if there are an odd number, to handle cases like 32 that prime factor into [2,2,2,2,2]. Example usage c 2880 = [4, 4, 4, 45].

Bonus fun

As a massively ineffecient prime generator: primes = filter (> 1) . zipWith (-) [2..] $ map (product . c) [1..].

Answer 4

JavaScript ES6 112

c=n=>{with(a=[]){for(i=k=1;i++<n;)for(;1^n%i;n/=i)push(++k%2?pop()*i:i);k%2||push(pop()*pop());return k<3?[]:a}}

test=k=>{console.log("n = "+k);console.log(c(k))};
test(-1);
test(0);
test(2);
test(4);
test(64);
test(96);
test(32);

Answer 5

Haskell, 106 104 101 bytes

c x=2/=sum[1|0<-mod x<$>[1..x]]
(x:r)%n|c x,mod n x<1,d<-div n x,c d=x:g d|1<3=r%n
e%n=e
g n=[4..n]%n

Try it online!

Less golfed and explanation:

c x = 2 /= sum[1|0<-map(mod x)[1..x]] -- counts number of divisors of x and returns true for all non-primes

g n = f [4..n] n            -- call f with a list of factor candidates and n

f []    n = []              -- if there are no factor candidates, return the empty list
f (x:r) n                   -- for the factor candidate x ...
    | c x,                  --    check if x is composite
      (d,m) <- divMod n x,  --    set d = n div x and m = n mod x
      m < 1,                --    n is divided by x if m = 0
      c d                   --    check that d is composite or 1
    = x : f (x:r) d         -- if all those checks are true append x to the list and determine the composites for d
    | otherwise = f r n     -- otherwise check the next candidate

Answer 6

Javascript (ES6), 94 bytes

n=>{for(a=[],d=2,l=q=0;n>1;)n%d?d++:(n/=d,q&&(a[l++]=q*d),q=q?0:d);q&&l&&(a[l-1]*=q);return a}

Ungolfed:

n=>{ //function declaration
  for(
    a=[], //the list
    d=2, //current factor
    l= //next index of the list
    q=0; //stored factor
    n>1; //while n>1
  )
    n%d? //if the factor is not a factor of current n
      d++ //go to next factor
      :( //else
        n/=d, //remove the factor
        q&& //if a factor is stored,
          (a[l++]=q*d), //add multiple of the saved factor and current factor
        q=q?0:d //store factor if it doesn't exist
      ); //end else
   //implicit for loop close 
  q&& //if there is remaining factor
    l&& //if the input is not a prime
      (a[l-1]*=q); //place the factor in the last element in the list
  return a //return the list
} //end function

Answer 7

Vyxal 3, 23 bytes

{:1>|:KᶻṄȮȮ÷⁾Ḣh$Ȯ÷}Wᶻ2<

Try it Online!

Answer 8

Perl 6, 83 bytes

my&f=->\n {my \p=min grep {n%%$_&!is-prime $_|n/$_},2..^n;Inf>p??flat p,f n/p!![n]}

Note: uses the is-prime builtin

Try it online!