# 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.

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 . Shortest answer in bytes wins.

## Mathics, 24 bytes

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


Try it online!

• #^#2&@@@FactorInteger@#&[1] returns {1} in Mathematica. But it works in Mathics. – alephalpha May 12 '17 at 10:54
• @alephalpha Thanks, it wouldn't even have occurred to me to see whether Mathics implements FactorInteger differently. :) – Martin Ender May 12 '17 at 11:03

# 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

• Congrats on your first Brachylog answer! ...at least I think? – Fatalize May 12 '17 at 16:36
• @Fatalize: My 2nd I think. I had this one from before. Definitely my shortest one though :) – Emigna May 12 '17 at 16:46

# 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

• @Adnan is that the best link for "bytes" or is there a formatted code page somewhere? – Jonathan Allan May 12 '17 at 10:51
• Yeah, there is a code-page that displays all bytes. – Adnan May 12 '17 at 10:53
• Oh, how'd I miss it >_< Thanks ever so much :) – Jonathan Allan May 12 '17 at 10:53
• Does not work for 1. – Leaky Nun May 12 '17 at 11:00
• @LeakyNun fixed up with help :) – Jonathan Allan May 12 '17 at 14:10

## 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).

(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.

# MATL, 7 bytes

&YF^1X-


### 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).

• I assume the change means 1X- is redundant in the new release... also, that looks like set difference rather than intersection to me. – Ørjan Johansen Jun 9 '17 at 23:10
• @ØrjanJohansen Correct on both. Thanks! – Luis Mendo Jun 9 '17 at 23:26

# 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

• An alternate 6-byte solution in an attempt to find another method that would tie with yours (unfortunately failing): ÆfŒgZP. It has the same number of tokens but too many two-byte atoms ;) – hyper-neutrino May 12 '17 at 12:10
• ...and like my deleted 05ab1e entry it returns 1 for an input of 1 which is disallowed (the effect of performing an empty product). – Jonathan Allan May 12 '17 at 12:14
• :( Well, whoops, overlooked that. Darn. :P – hyper-neutrino May 12 '17 at 12:18

## 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.  ## mathematica 46 bytes #[[1]]^#[[2]]&/@If[#==1,#={},FactorInteger@#]&  Try it online! • Nice answer, but it's giving slightly incorrect output for some of the test cases. Currently your code outputs {}; {2}; {3}; {2}; {5}; {2,3}; {7}; {2}; {3}; {2,5}; {11}; {2,3}; {13}; ... but it should output {}; {2}; {3}; {4}; {5}; {2,3}; {7}; {8}; {9}; {2,5}; {11}; {4,3}; {13}; ... instead. – Kevin Cruijssen May 12 '17 at 14:37 • I think I fixed it – ZaMoC May 12 '17 at 14:58 • Seems to work in TIO indeed. +1 Oh, and welcome to PPCG, I see you're fairly new here. You've probably already seen it, but if not, Tips for golfing in Mathematica might be interesting to read through. Enjoy your stay! :) – Kevin Cruijssen May 12 '17 at 15:11 • If you find yourself accessing the components of # more than # itself, you can save a lot of bytes by using Apply (@@@) instead of Map (/@): #^#2&@@@If... – Martin Ender May 12 '17 at 20:32 # 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);


# 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


# Pari/GP, 28 bytes

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


Try it online!

# 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.

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

# 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 //@, ///@, ...