Factorize me!!!

In this task, you have to write a program, that computes the prime factors of a number. The input is a natural number 1 < n < 2^32. The output is a list of the prime factors of the number in the following format. Exponents must be omitted if they are 1. Only output prime-numbers. (Assuming, the input is 131784):

131784 = 2^3 * 3 * 17^2 * 19

Using the same amount of whitespace is not required, whitespaces may be inserted wherever appropriate. Your program should complete in less then 10 minutes for any input. The program with the shortest amount of characters wins.

-
Bonus points if your program can factor 68575999143494039776547449671727581799041142646129473261271699761332969809514505‌​42789808884504301075550786464802304019795402754670660318614966266413770127 in less than 73 days! – Joey Adams Apr 7 '11 at 2:08
@Joey Adams: The factorization starts out with 17*71*113*997*313597... – FUZxxl Apr 9 '11 at 15:48
@FUZxxl: I think you made a mistake copying the number. It's the product of two large primes. – Joey Adams Apr 9 '11 at 17:50
@Joey Can we use Shor's Algorithm? – muntoo May 3 '11 at 3:30
@Joey I accidentally spilled some coffee over my quantum computer, and my friend is using his to "hack into the US Government" or something unimportant, so, no. :( – muntoo May 3 '11 at 5:59
show 1 more comment

Ruby 1.9, 74 70 characters

``````#!ruby -plrmathn
\$_+=?=+\$_.to_i.prime_division.map{|a|a[0,a[1]]*?^}*?*
``````

Edits:

• (74 -> 70) Just use the exponent as slice length instead of explicitly checking for `exponent > 1`
-

Perl 5.10, 73 88

``````perl -pe '\$_=`factor \$_`;s%( \d+)\K\1+%-1-length(\$&)/length\$1%ge;y, -,*^,;s;\D+;=;'
``````

Takes input number from standard input. Will compute factors for multiple inputs if provided.

Counted as a difference to `perl -e`. 5.10 is needed for the `\K` regex metacharacter.

-
 +1 for using `factor`. – st0le Apr 7 '11 at 4:41 Shouldn't you count the `p` option? – Joey Apr 7 '11 at 7:52 @Joey indeed I should. Sorry about that. Fixing. – J B Apr 7 '11 at 15:06 Havenâ€™t tested this, but instead of `split/\D/,~factor \$_~;\$_="@_";` could you write `\$_=~factor \$_~;s/\D/ /g;`? (Of course replace `~` with the backtick.) – Timwi Apr 9 '11 at 0:35 You mean `\$_=`factor \$_`;s/\D/ /g;`? Dual backtick encasing helps. – eBusiness Apr 9 '11 at 11:37
show 1 more comment

OCaml, 201 characters

A direct imperative translation of the best Python code:

``````let(%)s d=if!d>1then Printf.printf"%s%d"s!d
let f n=let x,d,e,s=ref n,ref 1,ref 0,ref"="in""%x;while!d<65536do
incr d;e:=0;while!x mod!d=0do x:=!x/ !d;incr e
done;if!e>0then(!s%d;"^"%e;s:="*")done;!s%x
``````

For example,

``````# f 4294967292;;
4294967292=2^2*3^2*7*11*31*151*331- : unit = ()
``````

(note that I've omitted outputting the final endline.) Just for fun, at 213 characters, a purely functional version, thoroughly obfuscated through liberal use of operators:

``````let(%)s d=if d>1then Printf.printf"%s%d"s d
let f x=let s=ref"="in""%x;let rec(@)x d=if d=65536then!s%x else
let rec(^)x e=if x/d*d<x then x,e else x/d^e+1in
let x,e=x^0in if e>0then(!s%d;"^"%e;s:="*");x@d+1in x@2
``````
-

Python, 140135 133 chars

``````M=N=input()
s=''
f=1
while f<4**8:
f+=1;e=0
while N%f<1:e+=1;N/=f
if e:s+='*%d'%f+'^%d'%e*(e>1)
print M,'=',(s+'*%d'%N*(N>1))[1:]
``````
-
 I think the output requires some more spaces, e.g. `' * %d'`... And two more things: `65536 == 4**8`; Line 7: `if e:s+='*%d'%f+'^%d'%e*(e>1)` – BlaXpirit Apr 7 '11 at 13:48 @BlaXpirit: "same amount of whitespace is not required". Thanks for the other two, I'll incorporate them. – Keith Randall Apr 7 '11 at 16:56

PHP, 112

``````echo\$n=\$_GET[0],'=';\$c=0;for(\$i=2;;){if(\$n%\$i<1){\$c++;\$n/=\$i;}else{if(\$c){echo"\$i^\$c*";}\$c=0;if(++\$i>\$n)break;}}
``````

118

``````echo \$n=\$_GET[0],'=';for(\$i=2;;){if(!(\$n%\$i)){++\$a[\$i];\$n/=\$i;}else{if(\$a[\$i])echo "\$i^\$a[\$i]*";\$i++;if(\$i>\$n)break;}}
``````
-

J, 72

``````(":*/f),'=',([,'*',])/(":"0~.f),.(('^',":)`(''"0)@.(=&1))"0+/(=/~.)f=.q:161784
``````

Typical J. Two characters to do most of the work, sixty characters to present it.

Edit: Fixed the character count.

-
This doesn't look like 62 characters to me. Even when assuming `161784` is your input, it's still 72 characters. – Ventero Apr 8 '11 at 16:27
Wouldn't it be shorter with `|: __ q: y`? – Eelvex Apr 9 '11 at 12:24
@Ventero: typical JB. Two hours to golf the damned thing, fifteen seconds to mess up the character count. – J B Apr 16 '11 at 19:41

Python 119 Chars

``````M=N=input()
i=1
s=""
while N>1:
i+=1;c=0
while N%i<1:c+=1;N/=i
if c:s+=" * %d"%i+['','^%d'%c][c>1]
print M,'=',s[3:]
``````
-
That's what I tried first, but it is too slow for big primes, like 4294967291. – Keith Randall Apr 7 '11 at 5:56
@Keith The question allows upto 10 minutes. Will this take more than 10 minutes for the worst case? – fR0DDY Apr 7 '11 at 7:01
It took 32 minutes on my machine for that number. – Keith Randall Apr 7 '11 at 16:54

Un-Golfed C (342 bytes)

``````long long n,i,e;
char str[100];
char tmp[99];
main(){
scanf("%lld",&n);
printf("%lld=",n);
for(i=2;i*i<=n;i++){
for(e=0;0==n%i;n/=i,e++);
e>1?sprintf(tmp,"*%lld^%lld",i,e),strcat(str,tmp):e==1&&sprintf(tmp,"*%lld",i)&&strcat(str,tmp);
}
n>1&&sprintf(tmp,"*%lld",n)&&strcat(str,tmp);
puts(str+1);
}
``````

Just for fun! :-)

-

PHP, 236 characters

``````\$f[\$n=\$c=\$argv[1]]++;echo"\$n=";while(\$c){\$c=0;foreach(\$f as\$k=>\$n)for(\$r=~~(\$k/2);\$r>1;\$r--){if(\$k%\$r==0){unset(\$f[\$k]);\$f[\$r]++;\$f[\$k/\$r]++;\$c=1;break;}}}foreach(\$f as\$k=>\$n)if(--\$n)\$f[\$k]="\$k^".++\$n;else\$f[\$k]=\$k;echo implode("*",\$f);
``````

Output for 131784: 2^3*3*17^2*19

Completes all numbers within a few seconds while testing.

``````4294967296=2^32
Time: 0.000168
``````

Input was never specified, so I chose to call it using command line arguments.

``````php factorize.php 4294967296
``````
-

JavaScript, 124122 119

``````for(s='',i=2,o=p=prompt();i<o;i++){for(n=0;!(p%i);n++)p/=i;n?s+=i+(n-1?'^'+n:'')+'*':0}alert(s.substring(0,s.length-1))
``````
-

Scala 374:

``````def f(i:Int,c:Int=2):List[Int]=if(i==c)List(i)else
if(i%c==0)c::f(i/c,c)else f(i,c+1)
class A(val v:Int,val c:Int,val l:List[(Int,Int)])
def g(a:A,i:Int)=if(a.v==i)new A(a.v,a.c+1,a.l)else new A(i,1,(a.v,a.c)::a.l)
a.l.map(p=>if(p._2==1)p._1 else p._1+"^"+p._2).mkString("", "*", "")
``````

ungolfed:

``````def factorize (i: Int, c: Int = 2) : List [Int] = {
if (i == c) List (i) else
if (i % c == 0) c :: f (i/c, c) else
f (i, c+1)
}
class A (val value: Int, val count: Int, val list: List [(Int, Int)])
def g (a: A, i: Int) =
if (a.value == i)
new A (a.value, a.count + 1, a.list) else
new A (i, 1, (a.value, a.count) :: a.list)
val a = (new A (r.head, 1, Nil: List[(Int,Int)]) /: (r.tail :+ 0)) ((a, i) => g (a, i))
a.l.map (p => if (p._2 == 1) p._1 else
p._1 + "^" + p._2).mkString ("", "*", "")
``````
-

JavaScript, 107

``````n=prompt()
s=n+'='
c=0
for(i=2;;){if(n%i<1){c++
n/=i}else{if(c)s+=i+'^'+c+'*'
c=0
if(++i>n)break}}
``````

120

``````n=prompt()
o={2:0}
for(i=2,c=n;i<=c;)!(c%i)?++o[i]?c/=i:0:o[++i]=0
s=n+'='
for(i in o)s+=o[i]?i+'^'+o[i]+'*':''
Has a trailing `*` in the output and prints the exponent even if it's 1. – Ventero Apr 9 '11 at 8:54
no need to downvote. There's nowhere that said that it couldn't print the exponent if it's 1. Also, the trailing `*` assumes multiplying by `1`. If it's that big an issue, I'll fix it. – zzzzBov Apr 9 '11 at 17:47
»in the following format« in the task description pretty much implies that an exponent of `1` should not be printed. And no, a trailing `*` is also against that. If one could choose the output format that freely, then shelling out to `factor(1)` would be the easiest one. Answers can only reasonably compared if they all solve the same problem. – Joey Apr 9 '11 at 23:13
``````load"ecmx.ub":run
Output format is not as specified. For 131784 it outputs `2 * 2 * 2 * 3 * 17 * 17 * 19` here instead of the requested format. Also it show a prompt on the screen which should not be there. – Joey Apr 12 '11 at 14:51