Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

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.
share|improve this question
1  
What output are you looking for if gcd(n,m) == 1? –  undergroundmonorail May 6 at 15:12
    
Is it okay if I exit with an exception? It would save me a few bytes. –  undergroundmonorail May 6 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 at 16:04
    
Do not exit with an exception. Output nothing :) –  durron597 May 6 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 at 8:07

19 Answers 19

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.

share|improve this answer
    
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 at 19:59
1  
You can save 1 character by changing while g<a and g<b: to while(g<a)*(g<b): –  Rainbolt May 6 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 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 at 1:50
    
@isaacg You seem to be right, thank you! –  Tal May 8 at 11:41

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.

share|improve this answer
    
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 at 21:50
    
Also, you can use $* instead of ARGV. –  daniero May 11 at 17:05

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

share|improve this answer
1  
What about …`a`+'^'+`f.count(a)`…? –  U2744 SNOWFLAKE May 6 at 18:09
    
@minitech Thanks! –  Rainbolt May 6 at 18:41
    
Pretty clean, I like it –  qwr May 7 at 2:18
    
@qwr Thanks. I hope I can understand the other Python answers String formatting and shave a few characters. –  Rainbolt May 7 at 13:04
1  
And now you don't need to use f at all :p (why is f='' still there?) –  Nolen Royalty May 8 at 14:52

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"
share|improve this answer
    
Hey can you try testing f(158,237) please –  durron597 May 6 at 21:25
    
It is space delimited with exponents (it just happens to have a lot of space) " 79^1" –  MT0 May 6 at 21:29
    
Right, the other solutions don't have that and neither does the example. Please fix :) –  durron597 May 6 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 at 21:35
2  
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? –  Cory May 6 at 21:49

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++);
    }
}
share|improve this answer
    
Nice, thanks :) –  Geobits May 6 at 19:46
    
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 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 at 19:59
2  
You can replace m/=i;i=1; with m/=i--; It will run faster too :) –  durron597 May 6 at 20:49
1  
Are the braces after the first for loop necessary? –  Ypnypn May 7 at 21:07

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();
    }
}
share|improve this answer

PowerShell - 82

$a,$b=$args
2..$a|%{$p=0;while(!($a%$_+$b%$_)){$a/=$_;$b/=$_;$p++}if($p){"$_^$p"}}
share|improve this answer
    
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 at 20:46

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)
];
share|improve this answer
    
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 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.) –  Cory May 12 at 14:29

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
share|improve this answer

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
share|improve this answer
    
⊎ is a symbol in perl? I didn't know that. –  durron597 May 11 at 16:27
    
@durron597 Only Perl 6 :) –  Mouq May 11 at 16:31

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.

share|improve this answer
    
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 at 14:31
    
@Mouq I've never seen a language with so much redundancy... thanks :) –  Tal May 11 at 17:41

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.

share|improve this answer

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.
share|improve this answer

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++;
share|improve this answer
    
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 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 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 at 21:30

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;
}
share|improve this answer
    
Do you need &&i<=b? –  durron597 May 9 at 3:00
    
Well I'll be... you're right, you don't: if i > b, then b % i != 0 ...thanks :) –  laindir May 9 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 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 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 at 0:05

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.

share|improve this answer
1  
What about …`a`+'^'+`f.count(a)`…? –  U2744 SNOWFLAKE May 6 at 18:10
    
I have no idea how I missed that. Jeez. Thanks. –  undergroundmonorail May 6 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 ":""}"
}
share|improve this answer
    
Surprised you chose to port Geobits' solution instead of mine, as mine is 56 characters shorter –  durron597 May 9 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  
share|improve this answer

Shell script, with gnu factor and gnu wdiff (may not be on all systems):

F=$(mktemp)
factor $1 > $F
factor $2 | wdiff -1 -2 $F -
share|improve this answer
1  
factor is not allowed, is it? –  martijnn2008 May 7 at 18:28
    
The other answers don't call factoring or gcd functions. If I can use them, I can answer in Ruby with 90 bytes: require'prime' (newline) puts ARGV.map(&:to_i).reduce(:gcd).prime_division.map{|e|e.join'^'}.join' '. –  kernigh May 9 at 20:33

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.