Maximal mutually co-prime factorization

Question

Definitions

• Two numbers are co-prime if their only positive common divisor is 1.
• A list of numbers is mutually co-prime if every pair of numbers within that list are co-prime with each other.
• A factorization of number n is a list of numbers whose product is n.

Task

Given a positive number n, output the mutually co-prime factorization of n with the maximum length that does not include 1.

Example

For n=60, the answer is [3,4,5], because 3*4*5=60 and no other mutually co-prime factorization without 1 has length greater than or equal to 3, the length of the factorization.

Rules and freedoms

• You can use any reasonable input/output format.
• The entries in the output list do not need to be sorted.

Testcases

n   output
1   []
2   [2]
3   [3]
4   [4]
5   [5]
6   [2, 3]
7   [7]
8   [8]
9   [9]
10  [2, 5]
11  [11]
12  [3, 4]
13  [13]
14  [2, 7]
15  [3, 5]
16  [16]
17  [17]
18  [2, 9]
19  [19]
20  [4, 5]
21  [3, 7]
22  [2, 11]
23  [23]
24  [3, 8]
25  [25]
26  [2, 13]
27  [27]
28  [4, 7]
29  [29]
30  [2, 3, 5]
31  [31]
32  [32]
33  [3, 11]
34  [2, 17]
35  [5, 7]
36  [4, 9]
37  [37]
38  [2, 19]
39  [3, 13]
40  [5, 8]
41  [41]
42  [2, 3, 7]
43  [43]
44  [4, 11]
45  [5, 9]
46  [2, 23]
47  [47]
48  [3, 16]
49  [49]
50  [2, 25]
51  [3, 17]
52  [4, 13]
53  [53]
54  [2, 27]
55  [5, 11]
56  [7, 8]
57  [3, 19]
58  [2, 29]
59  [59]
60  [3, 4, 5]
61  [61]
62  [2, 31]
63  [7, 9]
64  [64]
65  [5, 13]
66  [2, 3, 11]
67  [67]
68  [4, 17]
69  [3, 23]
70  [2, 5, 7]
71  [71]
72  [8, 9]
73  [73]
74  [2, 37]
75  [3, 25]
76  [4, 19]
77  [7, 11]
78  [2, 3, 13]
79  [79]
80  [5, 16]
81  [81]
82  [2, 41]
83  [83]
84  [3, 4, 7]
85  [5, 17]
86  [2, 43]
87  [3, 29]
88  [8, 11]
89  [89]
90  [2, 5, 9]
91  [7, 13]
92  [4, 23]
93  [3, 31]
94  [2, 47]
95  [5, 19]
96  [3, 32]
97  [97]
98  [2, 49]
99  [9, 11]

Scoring

This is code-golf. Shortest answer in bytes wins.

Answer 1

Mathics, 24 bytes

#^#2&@@@FactorInteger@#&

Try it online!

Answer 2

Brachylog, 4 bytes

ḋḅ×ᵐ

Try it online!

Explanation

       # output is the list of
  ×ᵐ   # products of each
 ḅ     # block of consecutive equal elements
ḋ      # of the prime factors
       # of the input

Answer 3

05AB1E, 3 5 bytes

+2 bytes to fix the edge case of 1. Thanks to Riley for the patch (and for the test suite, my 05ab1e is not that strong!)

ÒγP1K

Test suite at Try it online!

How?

Ò     - prime factorisation, with duplicates
 γ    - split into chunks of consecutive equal elements
  P   - product of each list
   1  - literal one
    K - removed instances of top from previous
      - implicitly display top of stack

Answer 4

CJam, 9 bytes

{mF::#1-}

Try it online!

Simply separates the input into its constituent prime powers and removes 1s (only necessary for input 1).

Answer 5

Haskell, 51 bytes

(2#) is an anonymous function taking an integer and returning a list.

Use as (2#) 99.

m#n|m>n=[]|x<-gcd(m^n)n=[x|x>1]++(m+1)#div n x
(2#)

Try it online!

Inspired by the power trick some people used in the recent squarefree number challenge.

• m#n generates factors of n, starting with m.
• If m>n, we stop, concluding we've already found all factors.
• x=gcd(m^n)n is the largest factor of n whose prime factors are all in m. Note that because smaller m are tested first, this will be 1 unless m is prime.
• We include x in the resulting list if it's not 1, and then recurse with the next m, dividing n by x. Note that x and div n x cannot have common factors.
• (2#) takes a number and starts finding its factors from 2.

Answer 6

MATL, 7 bytes

&YF^1X-

Try it online! Or verify all test cases.

Explanation

Consider input 80 as an example.

&YF    % Implicit input. Push array of unique prime factors and array of exponents
       % STACK: [2 3 5], [4 0 1]
^      % Power, element-wise
       % STACK: [16 1 5]
1      % Push 1
       % STACK: [16 1 5], 1
X-     % Set difference, keeping order. Implicitly display
       % STACK: [16 5]

---

EDIT (June 9, 2017): YF with two outputs has been modified in release 20.1.0: non-factor primes and their (zero) exponents are skipped. This doesn't affect the above code, which works without requiring any changes (but 1X- could be removed).

Answer 7

Jelly, 5 bytes

ÆF*/€

Test suite at Try it online!

How?

ÆF*/€ - Main link: n
ÆF    - prime factors as [prime, exponent] pairs
   /€ - reduce €ach with:
  *   - exponentiation

Answer 8

Alice, 10 bytes

Ifw.n$@EOK

Try it online!

Unfortunately, this uses code points as integer I/O again. The test case in the TIO link is input 191808 which decomposes into 64, 81 and 37. Note that this solution prints the prime powers in order from largest to smallest prime, so we get the output %Q@.

For convenience, here is a 16-byte solution with decimal I/O which uses the same core algorithm:

/O/\K
\i>fw.n$@E

Try it online!

Explanation

As the other answers, this decomposes the input into prime powers.

I      Read a code point as input.
f      Compute its prime factorisation a prime/exponent pairs and push them
       to the stack in order from smallest to largest prime.
w      Remember the current IP position on the return address stack. This
       starts a loop.
  .      Duplicate the current exponent. This will be zero once all primes
         have been processed.
  n$@    Terminate the program if this was zero.
  E      Raise the prime to its corresponding power.
  O      Output the result as a character.
K      Return to the w to run the next loop iteration.

Answer 9

mathematica 46 bytes

#[[1]]^#[[2]]&/@If[#==1,#={},FactorInteger@#]&

Try it online!

Answer 10

PHP, 62 Bytes

prints a associative array with the prime as key and how often the prime is use as value and nothing for input 1

for($i=2;1<$n=&$argn;)$n%$i?++$i:$n/=$i+!++$r[$i];print_r($r);

Try it online!

Output for 60

Array
(
    [2] => 2
    [3] => 1
    [5] => 1
)

PHP, 82 Bytes

for($i=2;1<$n=&$argn;)$n%$i?++$i:$n/=$i+!($r[$i]=$r[$i]?$r[$i]*$i:$i);print_r($r);

Try it online!

prints nothing for input 1 if you wish a empty array instead and a sorted array it will be a little longer

for($r=[],$i=2;1<$n=&$argn;)$n%$i?++$i:$n/=$i+!($r[$i]=$r[$i]?$r[$i]*$i:$i);sort($r);print_r($r);

Answer 11

Actually, 6 bytes

w⌠iⁿ⌡M

Try it online!

Explanation:

w⌠iⁿ⌡M
w       factor into [prime, exponent] pairs
 ⌠iⁿ⌡M  for each pair:
  i       flatten
   ⁿ      prime**exponent

Answer 12

Pari/GP, 28 bytes

n->[x[1]^x[2]|x<-factor(n)~]

Try it online!

Answer 13

miniML, 47 bytes

Challenges involving prime factorization are terribly over-represented here, so we are all sadly forced to have factorization in the standard library.

fun n->map(fun p->ipow(fst p)(snd p))(factor n)

Note that the 'mini' in miniml refers to the size of the feature set, not the size of source code written in it.

Answer 14

Ruby, 61 bytes

require 'prime'
->n{(2..n).select{|e|n/e.to_f%1==0&&e.prime?}}

I'm really disappointed after looking 6-7 byte solutions -))

Answer 15

Mathematica, 24 bytes

Power@@@FactorInteger@#&

Too bad @@@* is not a thing. Also, I'd like /@*, @@*, and in fact, change @@@ to /@@, //@ to @@@ or whatever and add the infinite family of //@, ///@, ...