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.

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

Scoring

This is . Shortest answer in bytes wins.

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

Mathics, 24 bytes

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

Try it online!

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

Jelly, 5 bytes

ÆF*/€

Test suite at Try it online!

How?

Æ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 ;) 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). May 12 '17 at 12:14
• :( Well, whoops, overlooked that. Darn. :P 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.

Try it online!

Output for 60

Array
(
 => 2
 => 1
 => 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^x|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 //@, ///@, ...