# Print the prime factorization of the greatest common divisor of two numbers

Title says it all. Two input 32-bit positive integers m, n >= 2, output gcd(m,n) in prime factorization form.

## Input

Command line args or 1 line of stdin okay, whatever's better for golf.

## Output

Single space delimited with exponents (no additional spaces). Output nothing if the inputs are relatively prime.

Examples:

$./factorize 96 162 2^1 3^1$ ./factorize 14 15

$./factorize 196 294 2^1 7^2  ## Rules • You may not use external resources, math libraries or built-in functions for factorization or GCD. Examples: Java, no java.lang.Math. ruby, no prime_division, perl, no factor, etc. • What output are you looking for if gcd(n,m) == 1? – undergroundmonorail May 6 '14 at 15:12 • Is it okay if I exit with an exception? It would save me a few bytes. – undergroundmonorail May 6 '14 at 15:29 • Actually, I've changed my approach and have no need to exit with an exception. Others might want to know, though. – undergroundmonorail May 6 '14 at 16:04 • Do not exit with an exception. Output nothing :) – durron597 May 6 '14 at 16:05 • Technically, q:a+.b or __ q:a+.b in J uses no external resources or math libraries, but I won't post it, since it's too far from the spirit of the question. I just thought I'd share it here. – ɐɔıʇǝɥʇuʎs May 12 '14 at 8:07 ## 19 Answers # Python 3, 255250 237226188180150142137 136 chars a,b=map(int,input().split()) t,g='',1 while g<a: g,p=g+1,0 if a%g+b%g<1: while a%g+b%g<1:a/=g;b/=g;p+=1 t+='%d^%d '%(g,p) print(t)  It's amazing how much I could shorten this by just skipping stuff (like, you know, finding the gcd)! Also I could reduce 10 more chars by making this a function that expects 2 ints, like some other answers, instead of reading from stdin. • This is intense! I'm learning a lot by watching your edits and trying to beat you lol. I think you might have this one though (out of the Python answers) – Rainbolt May 6 '14 at 19:59 • You can save 1 character by changing while g<a and g<b: to while(g<a)*(g<b): – Rainbolt May 6 '14 at 20:05 • @Rusher Thanks mate! Your answer is the one that motivated me to work harder on this :) Also the trick you recommended inspired me to figure out the a%g+b%g bit – Tal May 6 '14 at 20:25 • I don't think the else clause is necessary. else:g+=1 could just be g+=1, unless I'm missing something. – isaacg May 8 '14 at 1:50 • @isaacg You seem to be right, thank you! – Tal May 8 '14 at 11:41 # Ruby - 168117114101100 97 Edit: After thinking about it, realized I didn't need the sieve since the primality of the factor is taken care of in the factorization loop. Also, as informed by answers of others (laindir's and Tal's are the ones I had seen it in, though it looks like others have also done it), removed separate gcd calculation, since that also occurs in the factorization. Edit 2: Don't need do. Edit 3: Squeezing it down more. Edit 4: Pulled out one more space. Edit 5: upto instead of each; ?^ == "^"! a,b=ARGV.map{|i|i.to_i} 2.upto(a){|d|c=0 [c+=1,a/=d,b/=d]while a%d+b%d<1 print d,?^,c," "if c>0}  Output (same after edit): $ ruby factorize.rb 96 162
2^1 3^1
$ruby factorize.rb 14 15$ ruby factorize.rb 196 294
2^1 7^2


Certainly could be made better, but not bad for my first one.

• You can remove 4 bytes by changing map{|i|i.to_i} to map &:to_i. You can remove a 5th byte by not counting the newline at end of file; Ruby works without it. – kernigh May 9 '14 at 21:50
• Also, you can use $* instead of ARGV. – daniero May 11 '14 at 17:05 # Python 2 - 254252196185156151134126 121 i=1 a,b=map(int,raw_input().split()) while b:a,b=b,a%b while~-a: i+=1;j=0 while a%i<1:j+=1;a/=i if j:printi+'^'+j,  Interpreter repl.it Example Input - stdin 100 50 Example Output - stdout 2^1 5^2 • What about …a+'^'+f.count(a)…? – Ry- May 6 '14 at 18:09 • Pretty clean, I like it – qwr May 7 '14 at 2:18 • @qwr Thanks. I hope I can understand the other Python answers String formatting and shave a few characters. – Rainbolt May 7 '14 at 13:04 • Swap f.append(i) for f+=[i] to save 5 characters. – Nolen Royalty May 8 '14 at 4:36 • And now you don't need to use f at all :p (why is f='' still there?) – Nolen Royalty May 8 '14 at 14:52 # Java - 184 175 This is inspired by @Geobits (and a little of @Tal's answer) answer, but enough of it is different that I decided to create my own answer. class G{public static void main(String[]a){for(Integer i=1,q,n=i.valueOf(a[0]),m=i.valueOf(a[1]);m>=++i;System.out.print(q>0?i+"^"+q+" ":""))for(q=0;n%i+m%i<1;n/=i,m/=i)q++;}}  Ungolfed (sort of) with (human verification) test harness: class G { public static void mainMethod(String[] a) { for (Integer i = 1, q, n = i.valueOf(a[0]), m = i.valueOf(a[1]); m >= ++i; System.out.print(q > 0 ? i + "^" + q + " " : "")) for (q = 0; n % i + m % i < 1; n /= i, m /= i) q++; } public static void main(String[] a) { m(3, 3); m(196, 294); m(294, 196); m(14, 15); m(15, 14); m(96, 162); m(162, 96); m(300, 400); m(400, 300); m(100, 100); m(7, 7); m(4, 8); } public static void m(int one, int two) { mainMethod(new String[] { String.valueOf(one), String.valueOf(two) }); System.out.println(); } }  # dc, 96 bytes ?sbsa2sf[q]sk[lalf~lblf~szrlz+0<ksbsale1+selsx]ss[lfn[^]Plen[ ]P]sp[0selsxle0<plf1+dsflb!<w]dswx  It reads one line of standard input. Its output does not end with a newline. (EDIT: It does also output an extra space after every factorization. Some of the other answers trim the space, but this one doesn't.) Example: $ echo 301343045 421880263 | dc factorize.dc
1021^1 59029^1 $ Code with comments: # dc(1) is a stack language, like Forth. Programs push values on the # stack, then operate on them. For example, to calculate # (2 + 3) * (9 - 4) # the dc code is # [2 3 + 9 4 - *] # [?] reads a line of input. We expect two integers >= 2. # [sb sa] stores the integers in variables. ? sb sa # a, b = two integers from input # This program sucks common factors from a and b, looping for # f = 2, 3, 4, 5, and so on. This method only sucks prime factors, # but wastes time when f is not prime. 2 sf # f = 2 # Code in [...] does not run until the program calls it. # k = code to break a loop [ q # [q] breaks two levels of [...] ] sk # k = break # s = loop to suck factor f from a and b # This loop increments e, the exponent for factor f. # Please set e = 0 before entering this loop. [ # [la lf] puts ( a f ) on the stack. # [~] does division and remainder. # STACK: la lf ~ # ( a/f a%f ) lb lf ~ # ( a/f a%f b/f b%f ) # [r] swaps the top two stack values. # Hold z = b%f and swap a%f with b/f. # STACK: sz r lz # ( a/f b/f a%f b%f ) # f is a common factor if a%f and b%f are zero. Because a and b are # non-negative, a%f and b%f are zero only if a%f+b%f is zero. # STACK: + # ( a/f b/f a%f+b%f ) # Call k to break loop unless a%f+b%f is zero. [<k] conditionally # calls k if the comparison is true. Comparisons in dc are # backwards, so [3 0 <k] would check 0 < 3. Because a%f+b%f is never # negative, [0 <k] is golf for [0 !=k]. # STACK: 0 <k # ( a/f b/f ) # f is a common factor, so suck it! sb sa # a = a/f, b = b/f, STACK: ( ) le 1 + se # increment e, the exponent for this factor ls x # continue loop, [x] executes s ] ss # s = loop # p = code to print "f^e " [ # [n] prints a number without a newline. # [P] prints a string. lf n [^]P le n [ ]P # DEBUG: Uncomment to print a and b. #[(a = ]P la n [, b = ]P lb n [)]P 10P ] sp # p = print # w = loop to iterate factors [ # Call s loop to suck factor f from a and b, and set exponent e. 0 se # e = 0 ls x # call s loop # DEBUG: Uncomment [c] to clear the stack. Loop s leaves two junk # values ( a/f b/f ) on the stack. Deleting [c] for code golf saves # 1 byte but leaks junk on the stack. #c # Print "f^e " if 0 < e. Comparisons in dc are backwards, so # [0 le <p] would check e < 0, [le 0 <p] checks 0 < e. le 0 <p # Increment f. [d] duplicates top value on stack. # STACK: lf 1 + # ( f+1 ) d # ( f+1 f+1 ) sf # ( f ) as f+1 becomes f # Continue loop if b >= f. This is golf for f <= a and f <= b, as # extra iterations of the loop cause no harm. # STACK: lb # ( f b ) !<w # ( ), continue loop if not b < f ] d sw # w = loop; STACK: ( w ) x # enter loop unconditionally; STACK: ( ) at entrance  ## PowerShell - 82 $a,$b=$args
2..$a|%{$p=0;while(!($a%$_+$b%$_)){$a/=$_;$b/=$_;$p++}if($p){"$_^$p"}}

• This one is short and easy to read. It pipes the range 2..$a into a Foreach-Object loop %{...}. The loop collects the values of if($p){"$_^$p"}. – kernigh May 9 '14 at 20:46

# JavaScript (ECMAScript 6 Draft) - 89 Characters

f=(m,n,i=2,k=0)=>(m%i|n%i?(k?i+'^'+k+' ':'')+(i>m?'':f(m,n,i+1)):f(m/i,n/i,i,k+1)).trim()


Converts the original (iterative) answer, below, into a recursive one.

Explanation

f=(m,n,i=2,k=0)=>           // A function with arguments m and n and optional arguments
// i (defaults to 2) and k (defaults to 0)
(
m%i|n%i                 // if i is not a divisor of m or n then:
?(k?i+'^'+k+' '       //   if k is non-zero append  "i^k " to the output
:'')               //   else append nothing
+(i>m?''            //   if i>m then terminate
:f(m,n,i+1))   //   else increment i and reset k to 0
:f(m/i,n/i,i,k+1)     // else divide m and n by i and increment k
).trim()                  // finally strip any extra spaces from the output.


# Iterative Answer: JavaScript (ECMASCript 6) - 108 (or 121) 98 Characters

Version 2:

f=(m,n)=>{for(s='',i=1;++i<=m;s+=k?' '+i+'^'+k:'')for(k=0;m%i+n%i<1;k++)m/=i,n/=i;return s.trim()}


Version 1:

Answering the question as originally asked:

f=(m,n)=>{for(o=[],i=2;i<=m;)m%i|n%i?i++:(m/=i,n/=i,o[i]=(o[i]|0)+1);return o.map((x,i)=>i+"^"+x).join(' ')}


Or to comply with the rule changes after the fact:

f=(m,n)=>{for(o=[],i=2;i<=m;)m%i|n%i?i++:(m/=i,n/=i,o[i]=(o[i]|0)+1);return o.map((x,i)=>i+"^"+x).filter(x=>x).join(' ')}


Explanation

f=(m,n)=>                        // Create a function f with arguments m and n
{
o=[]                           // Initialise an empty array for the output
i=2                            // Start with a divisor of 2
for(;i<=m;)                    // Loop while the divisor is not greater than m
m%i|n%i                      // Test the bitwise OR of m%i and n%1 (i.e. whether
// at least one is non-zero)
?i++                       // If m%i>0 or n%i>0 then increment i
:(m/=i,                    // Otherwise: divide m by i;
n/=i,                    //                   n by i;
o[i]=(o[i]|0)+1);        // and add 1 to the i-th element of o
return o.map((x,i)=>i+"^"+x)   // finally map the sparse array o to a sparse array
// of the strings (index+"^"+value)
.filter(x=>x)          // turn sparse array into non-sparse array
.join(' ')             // then concatenate and return.
}


Output

f(96,162)
"2^1 3^1"

f(14,15)
""

f(80, 80)
"2^4 5^1"

f(196,294)
"2^1 7^2"

• Hey can you try testing f(158,237) please – durron597 May 6 '14 at 21:25
• It is space delimited with exponents (it just happens to have a lot of space) " 79^1" – MT0 May 6 '14 at 21:29
• Right, the other solutions don't have that and neither does the example. Please fix :) – durron597 May 6 '14 at 21:29
• Nothing in the question, as originally asked, defines how much whitespace is or is not allowed - as I see it, this meets the requirements as it is whitespace delimited with exponents. However, you're going to go and change the rules now aren't you? – MT0 May 6 '14 at 21:35
• Under the preexisting rules, one could say that this implementation omits the requirement "Output nothing if the inputs are relatively prime." Still seems wrong to deface golf code that came out so pretty. How brief can you make a filter() call? – Keen May 6 '14 at 21:49

# Perl 6: 90 characters, 94 bytes

sub MAIN(*@n){@n.any%$_||(my$p=$p⊎$_;@n»/=»$_;redo)for 2..@n[0];$p.pairs.fmt("%d^%d").say}


Somewhat de-golfed and commented:

sub MAIN (*@n) { # accept any number of input numbers as @n
(
# $p is a Bag, e.g., it holds the primes and the number of times each was added my$p = $p ⊎$_; # Add the prime to the bag
@n »/=» $_; # Divide all the input numbers by the prime redo # Redo the loop iteration with the same prime, in case # the numbers can be divided by it multiple times ) if @n.all %%$_ # Do the above only if all of @n are divisible by $_ for 2..@n[0]; # Do the above for all numbers from 2 .. @n[0]$p.pairs.fmt("%d^%d").say # Print join " ", "$prime^$count"
}


Usage is like:

$perl6 -e'sub MAIN(*@n){@n.any%$_||(my$p=$p⊎$_;@n»/=»$_;redo)for
2..@n[0];$p.pairs.fmt("%d^%d").say}' 51 153 3^1 17^1  • ⊎ is a symbol in perl? I didn't know that. – durron597 May 11 '14 at 16:27 • @durron597 Only Perl 6 :) – Mouq May 11 '14 at 16:31 # Perl, 14413311811497 93 ($a,$b)=<>=~/\d+/g;for(2..$a){for($n=0;$a%$_+$b%$_<1;$n++,$a/=$_,$b/=$_){}$n&&print"$_^$n ";}  Ungolfed version: ($a,$b)=<>=~/\d+/g; for(2..$a){
for($n=0 ;$a%$_+$b%$_<1 ;$n++,$a/=$_,$b/=$_) {}
$n&&print"$_^$n "; }  I've literally just started learning Perl just to answer this question (this is my first Perl code ever), so I suspect that this can be golfed down further. • Yes, I haven't looked at your code closely, but foreach is always synonymous with for in Perl 5, so that should cut off 4 chars :) – Mouq May 11 '14 at 14:31 • @Mouq I've never seen a language with so much redundancy... thanks :) – Tal May 11 '14 at 17:41 # Java : 247 241 Keeps track of factors in an array and just prints them out in a loop. Decent size for Java, it seems. class G{public static void main(String[]a){Integer i=1;int n=i.valueOf(a[0]),m=i.valueOf(a[1]),f[]=new int[n>m?n:m+1];for(;m>=++i||n>i;){if(n%i+m%i<1){f[i]++;n/=i;m/=i--;}}for(i=2;i<f.length;System.out.print(f[i]>0?i+"^"+f[i]+" ":""),i++);}} // line breaks below class G{ public static void main(String[]a){ Integer i=1;int n=i.valueOf(a[0]),m=i.valueOf(a[1]),f[]=new int[n>m?n:m+1]; for(;m>=++i||n>i;){ if(n%i+m%i<1){ f[i]++;n/=i;m/=i--; } } for(i=1;i<f.length;System.out.print(f[i]>0?i+"^"+f[i]+" ":""),i++); } }  • You can actually leave the other variables as int, you lose 4 to the int  but you gain them back with new int[ -> new Integer[ so it's a wash. – durron597 May 6 '14 at 19:55 • Yeah, and I got another three by switching n%i<1&&m%i<1 to n%i+m%i<1. – Geobits May 6 '14 at 19:59 • You don't need the (). If n==m, it'll default to m+1 anyway. – Geobits May 6 '14 at 20:13 • You can replace m/=i;i=1; with m/=i--; It will run faster too :) – durron597 May 6 '14 at 20:49 • Are the braces after the first for loop necessary? – Ypnypn May 7 '14 at 21:07 # JavaScript (ECMAScript 5) 170164163 113 I pretty much couldn't resist following MT0's lead. I had considered recursion before, but it had seemed too easy to mess up. And it really is. The slightest variation wrecks everything. There's a fiddle for those who like fiddles. function f(a,b,i,e){return i?a%i|b%i?(e?i+'^'+e+' ':'')+(i>a?'':f(a,b,i+1,0)):f(a/i,b/i,i,e+1):f(a,b,2,0).trim()}  Ungolfed: function f(a,b,i,e){ return i // Check for factor. ?a%i|b%i // Check for indivisibility. ?( e // Check for exponent. ?i+'^'+e+' ' // Add the current factor to result string. :'' // Omit the current non-factor. )+( i>a // Check for termination state. ?'' // Stop recursion. :f(a,b,i+1,0) // Go to the next factor. ) :f(a/i,b/i,i,e+1) // Failed indivisibility check. Increment exponent and divide subject values. :f(a,b,2,0) // Add default factor and exponent. .trim() // Get rid of one extra space that's usually on the end. }  ### Old Version function f(a,b){for(var r=[],j=-1,i=2;i<=a;)a%i|b%i?++i:(r[j]&&r[j][0]==i?r[j][1]++:r[++j]=[i,1],a/=i,b/=i);for(j=0;i=r[j];++j)r[j]=i.join('^');return r.join(' ')}  Ungolfed: function f(a,b){ for(var r=[],j=-1,i=2;i<=a;) // We (mis)use conditional expression ?: instead of if(){}else{}. a%i|b%i ? // Bitwise OR saves one character over logical OR, where applicable. // In the truth case, i has become uninteresting. Just move on. ++i : // We don't mind hitting composites because their prime factors have already been drained from a and b. ( r[j]&&r[j][0]==i ? // Check if i is already a listed factor. r[j][1]++ : // Increment the exponent count. r[++j]=[i,1], // Otherwise, add a new factor with exponent 1. a/=i,b/=i // Drain a used-up factor from a and b. ); // The real work's done. Now we just format. for(j=0; i=r[j]; ++j) r[j]=i.join('^'); // Join each factor to its exponent. return r.join(' ') // Join all factors into result string. }  Here are a few tests: [ f(4, 12), f(80, 80), f(96,162), f(196,294) ];  • This recursive function failed on f(301343045, 421880263); probably because my browser will not let me recurse that deep. Stupid broken Firefox! – kernigh May 9 '14 at 21:00 • Certainly. In practice I'd only use a recursive function if I really needed some kind of stack, like for tree navigation or other inherently recursive data-structures. (Sure, numbers can be treated as recursive data-structures, but we have all kinds of nice abstractions to help us ignore that fact.) – Keen May 12 '14 at 14:29 # GolfScript, 68 bytes ~..),2>*${1$1$%3$2$%+!{.@@/@2$/.}*;}/;;]:D.&{.[~]D\/,("^"\++}%" "*  Note that this approach requires O(b2) time and space for integers “a” and “b”. At the cost of one extra byte, "only" O(b) time and space are necessary: ~.),2>31*${1$1$%3$2$%+!{.@@/@2$/.}*;}/;;]:D.&{.[~]D\/,("^"\++}%" "*  ### How it works ~. # Interpret the input string (“a” and “b”) and duplicate “b”. .),2> # Push the array [ 2 3 4 ... b ]. *$        # Repeat each element b times and sort: [ 2 ... 2 3 ... 3 ... b ... b ]
{         # For each element “d” of the array:
1$1$%   # Calculate a % d.
3$2$%   # Calculate b % d.
+!      # Add and negate.
{       # If both “a” and “b” are divisible by “d”:
.@@/  # Calculate a / d.
@2$/ # Calculate b / d. . # Create a dummy value. }* # ; # Pop the topmost stack element (non-divisor “d” or dummy value). }/ # ;;] # Pop “a” and “b” and collect the remaining stack elements in an array. :|.& # Save that array in “D” and intersect it with itself to deduplicate it. { # For each element “d” of “D”: .[~] # Push string "d" and array [d]. D\/,( # Split “D” around [d] and take the length minus 1. This count the occurrences. "^"\ # Push the string "^" and swap it between "d" and it's number of occurrences. ++ # Concatenate the three strings. }% # Collect all strings into an array. ]" "* # Join by spaces.  # Python 3 (123) This uses basically the same structure as Tal's answer. a,b=map(int,input().split()) s='';p=1 while p<a: c=0;p+=1 while a%p+b%p<1:a/=p;b/=p;c+=1 if c:s+='%d^%d '%(p,c) print(s)  It suffices to loop up to p=a-1, since we increment immediately to get p=a and a>=min(a,b). If b>a, there's no harm in trying useless values of p above a. In 2.X, I think we could save characters by printing each piece as we get it rather than accumulating a string: if c:print'%d^%d'%(p,c),. Python 3, unfortunately, doesn't seem to have a compact way to print without a trailing newline. # PHP, 96 <?php list(,$a,$b)=$argv;for($s=1;$s++<$a;$c&&print"$s^$c ")for($c=0;1>$a%$s+$b%$s;$a/=$s,$b/=$s)$c++;

• We got almost exactly the same code! My one improvement is to combine p=0;g+=1 into one line by starting g at 1 instead, which lets you then do g<a rather than g<=a. I hope you grow to like python. – xnor May 11 '14 at 21:10
• @xnor I missed your code. Indeed it's almost the same. I removed my python script. I hope i won't have to like python, I NEED braces – mleko May 11 '14 at 21:19
• No need to remove your code, you came up with it yourself. I also came up with basically the game thing as Tal, so it looks like this is just what the Python golf converges to. – xnor May 11 '14 at 21:30

# awk - 11511196 85

New version can only handle one line of input. Thanks to durron597 for pointing out that I only need to make sure i <= $1. {for(i=1;++i<=$1;)for(;$1%i+$2%i==0;f[i]++){$1/=i;$2/=i}$0=z;for(i in f)$i=i"^"f[i]}1


Ungolfed:

{
#skip finding gcd as a separate step, get it from the factors
for(i = 1; ++i <= $1;) { for(;$1 % i == 0 && $2 % i == 0; f[i]++) {$1 /= i;
$2 /= i; } }$0 = "";
for(i in f) {
$i = i "^" f[i]; } print; }  Previously could take pairs of numbers repeatedly {a=$1;b=$2;for($0=c;a-b;)if(a>b)a-=b;else b-=a;for(i=2;i<=a;i++){for(j=0;a%i==0;j++)a/=i;$0=$0(j?i"^"j" ":c)}}1


Ungolfed:

{
a = $1; b =$2;
$0 = ""; #rip off Euclid for(; a != b;) { if(a > b) { a = a - b; } else { b = b - a; } } #but not Eratosthenes for(i = 2; i <= a; i++) { for(j = 0; a % i == 0; j++) { a /= i; }$0 = $0 (j ? i "^" j " " : ""); } print; }  • Do you need &&i<=b? – durron597 May 9 '14 at 3:00 • Well I'll be... you're right, you don't: if i > b, then b % i != 0 ...thanks :) – laindir May 9 '14 at 13:19 • This program does not work with awk in OpenBSD 5.5, because NF=0; fails to delete$1 and $2. The output from echo 301343045 421880263 | awk -f factorize.awk | sed 's/ */ /g' is 5 7 1021^1 59029^1 because$1 is 5 and $2 is 7. The sed squeezes the extra spaces that come from printing$1022, $1023,$1024, ..., $59028 as empty strings joined by spaces. – kernigh May 9 '14 at 21:37 • Thanks @kernigh, it works in nawk, mawk, and gawk. Double-checked that posix says nothing about assigning to NF, and replaced with $0=z; – laindir May 12 '14 at 13:07
• @laindir That change fixes the program for me. Code golf does not require programs to be portable. Luckily $0=z; is the same number of characters as NF=0;. If $0=z; was longer, I would tell you to keep NF=0;. – kernigh May 15 '14 at 0:05

# Pip, 41 bytes

Not a competing answer, since language is newer than question. But that GolfScript mark of 68 needed to come down.

Fi2,++a{p:0T$|g%i{++pg/:i}Ipx.:i.'^.p.s}x  Output ends in a space; if that's a problem, the following version is also 41 bytes (including the -s flag): Fi2,++a{p:0T$|g%i{++pg/:i}IplAE:i.'^.p}l


Formatted, with explanations:

F i 2,++a {      For i in range(2,a+1); note ++ used to avoid parentheses in 2,(a+1)
p:0            p will store the greatest power of i that divides both numbers
T $+(g%i) { Loop till the sum of g%i is nonzero, where g is a list initialized from cmdline args ++p As long as g%i is [0 0], increment p... g/:i ...and divide both numbers in g by i } I p If p is nonzero, i went into both numbers at least once x.:i.'^.p.s Append i^p and a space to the result } x Print the result  Pip, unlike GolfScript, CJam, et al. is an imperative language with infix operators; it also takes some inspiration from array-programming languages. This task nicely displays both paradigms at work. (Note that the 2015-4-20 commit is needed to run this, since I just fixed a couple of bugs.) # Python 2 - 262 bytes n,m=input(),input() f=lambda i:set(filter(lambda x:i%x<1,range(1,i+1))) g=max(f(n)&f(m)) p=[] while g-1: p+=[min(filter(lambda x:x>1 and x%2!=(x==2)and not any(map(lambda y:x%y<1,range(2,x))),f(g)))] g/=p[-1] print ' '.join(a+^+p.count(a)for a in set(p))  Line 6 needs work. • What about …a+'^'+f.count(a)…? – Ry- May 6 '14 at 18:10 • I have no idea how I missed that. Jeez. Thanks. – undergroundmonorail May 6 '14 at 18:36 ## Groovy : 174 chars This is a port of Geobits' solution to Groovy 2.2.1: int i=1, n=args[0]as int, m=args[1]as int;s=n>m?n:m+1;f=new int[s];while(m>=++i||n>i){if(n%i+m%i<1){f[i]++;n/=i;m/=i--;}};(s-1).times{y=it+1;x=f[y];print"${x>0?"$y^$x ":""}"}


Here is the ungolfed version:

int i = 1, n = args[0] as int, m = args[1] as int

s = n>m?n:m+1
f = new int[s]

while (m>=++i||n>i) {
if (n%i+m%i<1) {
f[i]++;n/=i;m/=i--;
}
}
(s-1).times {
y=it+1
x=f[y]
print"${x>0?"$y^\$x ":""}"
}

• Surprised you chose to port Geobits' solution instead of mine, as mine is 56 characters shorter – durron597 May 9 '14 at 23:06

## R: 139

a=scan();q=1:a[1];n=max(q[!a[1]%%q&!a[2]%%q]);m=rep(0,n);for(i in 2:n){while(!n%%i){m[i]=m[i]+1;n=n/i};if(m[i])cat(paste0(i,"^",m[i])," ")}


With indentations:

a=scan() #Take space-separated numeric input from stdin
q=1:a[1]
n=max(q[!a[1]%%q&!a[2]%%q]) #gcd
m=rep(0,n)
for(i in 2:n){
while(!n%%i){ #prime factorization
m[i]=m[i]+1
n=n/i
}
if(m[i])cat(paste0(i,"^",m[i])," ")
}


Usage:

> a=scan();q=1:a[1];n=max(q[!a[1]%%q&!a[2]%%q]);m=rep(0,n);for(i in 2:n){while(!n%%i){m[i]=m[i]+1;n=n/i};if(m[i])cat(paste0(i,"^",m[i])," ")}
1: 196 294
3:
Read 2 items
2^1  7^2