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

• OEIS for the length of the output. Commented May 12, 2017 at 11:09
• OEIS for the flattened sequence. (With a leading 1.) Commented May 12, 2017 at 11:10
• Harder follow-up challenge: only adjacent pairs in the resulting list need to be co-prime. Commented May 12, 2017 at 11:12
• Is this just a factorization into prime powers? Commented May 12, 2017 at 16:06
• @PaŭloEbermann yes, it is. Commented May 12, 2017 at 16:08

## Mathics, 24 bytes

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


Try it online!

• #^#2&@@@FactorInteger@#&[1] returns {1} in Mathematica. But it works in Mathics. Commented May 12, 2017 at 10:54
• @alephalpha Thanks, it wouldn't even have occurred to me to see whether Mathics implements FactorInteger differently. :) Commented May 12, 2017 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? Commented May 12, 2017 at 16:36
• @Fatalize: My 2nd I think. I had this one from before. Definitely my shortest one though :) Commented May 12, 2017 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? Commented May 12, 2017 at 10:51
• Yeah, there is a code-page that displays all bytes. Commented May 12, 2017 at 10:53
• Oh, how'd I miss it >_< Thanks ever so much :) Commented May 12, 2017 at 10:53
• Does not work for 1. Commented May 12, 2017 at 11:00
• @LeakyNun fixed up with help :) Commented May 12, 2017 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. Commented Jun 9, 2017 at 23:10
• @ØrjanJohansen Correct on both. Thanks! Commented Jun 9, 2017 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 ;) Commented May 12, 2017 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). Commented May 12, 2017 at 12:14
• :( Well, whoops, overlooked that. Darn. :P Commented May 12, 2017 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. Commented May 12, 2017 at 14:37 • I think I fixed it Commented May 12, 2017 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! :) Commented May 12, 2017 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... Commented May 12, 2017 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 //@, ///@, ...