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

Question

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.

• undergroundmonorail: What output are you looking for if gcd(n,m) == 1?
• undergroundmonorail: Is it okay if I exit with an exception? It would save me a few bytes.
• undergroundmonorail: Actually, I've changed my approach and have no need to exit with an exception. Others might want to know, though.
• durron597: Do not exit with an exception. Output nothing :)
• ɐɔıʇǝɥʇuʎs: 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.

Answer 1

Python 3, (削除) 255 (削除ここまで) (削除) 250 (削除ここまで) (削除) 237 (削除ここまで) (削除) 226 (削除ここまで) (削除) 188 (削除ここまで) (削除) 180 (削除ここまで) (削除) 150 (削除ここまで) (削除) 142 (削除ここまで) (削除) 137 (削除ここまで) 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.

• Rainbolt: 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: You can save 1 character by changing while g<a and g<b: to while(g<a)*(g<b):
• Tal: @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
• izzyg: I don't think the else clause is necessary. else:g+=1 could just be g+=1, unless I'm missing something.
• avall: You can save another 3 characters indenting with space and Tab instead of space and double space.

Answer 2

Ruby - (削除) 168 (削除ここまで) (削除) 117 (削除ここまで) (削除) 114 (削除ここまで) (削除) 101 (削除ここまで) (削除) 100 (削除ここまで) 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.

• kernigh: 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.
• daniero: Also, you can use $* instead of ARGV.

Answer 3

Python 2 - (削除) 254 (削除ここまで) (削除) 252 (削除ここまで) (削除) 196 (削除ここまで) (削除) 185 (削除ここまで) (削除) 156 (削除ここまで) (削除) 151 (削除ここまで) (削除) 134 (削除ここまで) (削除) 126 (削除ここまで) 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:print`i`+'^'+`j`,

Interpreter

repl.it

Example Input - stdin

100 50

Example Output - stdout

2^1 5^2

• Ry-: What about ...`a`+'^'+`f.count(a)`...?
• qwr: Pretty clean, I like it
• Rainbolt: @qwr Thanks. I hope I can understand the other Python answers String formatting and shave a few characters.
• Nolen Royalty: Swap f.append(i) for f+=[i] to save 5 characters.
• Nolen Royalty: And now you don't need to use f at all :p (why is f='' still there?)

Answer 4

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();
 }
}

Answer 5

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

Answer 6

PowerShell - 82

$a,$b=$args
2..$a|%{$p=0;while(!($a%$_+$b%$_)){$a/=$_;$b/=$_;$p++}if($p){"$_^$p"}}

• kernigh: 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"}.

Answer 7

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"

• durron597: Hey can you try testing f(158,237) please
• MT0: It is space delimited with exponents (it just happens to have a lot of space) " 79^1"
• durron597: Right, the other solutions don't have that and neither does the example. Please fix :)
• MT0: 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?
• Keen: 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?

Answer 8

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

• durron597: ⊎ is a symbol in perl? I didn't know that.
• Mouq: @durron597 Only Perl 6 :)

Answer 9

Perl, (削除) 144 (削除ここまで) (削除) 133 (削除ここまで) (削除) 118 (削除ここまで) (削除) 114 (削除ここまで) (削除) 97 (削除ここまで) 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.

• Mouq: 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 :)
• Tal: @Mouq I've never seen a language with so much redundancy... thanks :)

Answer 10

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++);
 }
}

• durron597: 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.
• Geobits: Yeah, and I got another three by switching n%i<1&&m%i<1 to n%i+m%i<1.
• Geobits: You don't need the (). If n==m, it'll default to m+1 anyway.
• durron597: You can replace m/=i;i=1; with m/=i--; It will run faster too :)
• Ypnypn: Are the braces after the first for loop necessary?

Answer 11

JavaScript (ECMAScript 5) (削除) 170 (削除ここまで) (削除) 164 (削除ここまで) (削除) 163 (削除ここまで) 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)
];

• kernigh: This recursive function failed on f(301343045, 421880263); probably because my browser will not let me recurse that deep. Stupid broken Firefox!
• Keen: 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.)

Answer 12

GolfScript, 68 bytes

~..),2>*${11ドル$%32ドル$%+!{.@@/@2$/.}*;}/;;]:D.&{`.[~]D\/,(`"^"\++}%" "*

Note that this approach requires O(b²) 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*${11ドル$%32ドル$%+!{.@@/@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:
 11ドル$% # Calculate a % d.
 32ドル$% # 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.

Answer 13

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.

Answer 14

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++;

• xnor: 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.
• mleko: @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
• xnor: 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.

Answer 15

awk - (削除) 115 (削除ここまで) (削除) 111 (削除ここまで) (削除) 96 (削除ここまで) 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;
}

• durron597: Do you need &&i<=b?
• laindir: Well I'll be... you're right, you don't: if i > b, then b % i != 0 ...thanks :)
• kernigh: 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.
• laindir: Thanks @kernigh, it works in nawk, mawk, and gawk. Double-checked that posix says nothing about assigning to NF, and replaced with 0ドル=z;
• kernigh: @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;.

Answer 16

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

Answer 17

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.

• Ry-: What about ...`a`+'^'+`f.count(a)`...?
• undergroundmonorail: I have no idea how I missed that. Jeez. Thanks.

Answer 18

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 ":""}"
}

• durron597: Surprised you chose to port Geobits' solution instead of mine, as mine is 56 characters shorter

Answer 19

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