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.

• walpen: As an important test case you seemed to have missed, I assume the result for 32 is [4,8] (the first way I came up with fails that case).
• walpen: Also, I think if you made the challenge simply undefined for non-positive integers then the question would have less of "how many characters is if-then-else in your language?"
• Anthony Pham: @walpen Will edit momentarily
• Joffan: Should maybe add a test case like 42, where first composite factor is less than remaining single-prime factor (which just tripped up my attempt).

Answer 1

Jelly, 12 bytes

×ばつ2/

Try it online!

How it works

×ばつ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>|:KzṄȮȮ÷)Ḣh$Ȯ÷}Wz2<

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!

• Jo King: 78 bytes