Code Golf: Prime Factors of a Number?

C#, 69 x is input number int i=2;while(x>1)if(x%i++==0){x/=--i;Console. Write(i+(x>1? "x":""));}.

Very nice! – Alex Aug 20 '09 at 19:59 1 @Alex except it won't compile at all. – Alex B Aug 9 '10 at 4:23 @Alex B I just tried it, works fine.

Are you sure you declared the input x? – Yuriy Faktorovich Aug 9 '10 at 4:59 @Yuriy, it won't compile by itself, so this line is not a valid program and hence is not really a valid Code Golf challenge entry. – Alex B Aug 9 '10 at 5:14 2 @Yuriy that's the standard format for code golf and is a part of the challenge, nothing to do with "my prerogative".

– Alex B Aug 9 '10 at 23:41.

1 ~. @q: if you want unique factors, but yeah :) – ephemient Aug 20 '09 at 17:01 4 the example in the question shows 11 as factor twice. – Jimmy Aug 20 '09 at 17:02.

That doesn't look like any ANSI C I've ever seen. What kind of main() takes two ints as arguments? – Chris Lutz Aug 20 '09 at 20:46 2 Ah, and here is the trick: you can use 'char **argv' as an int, and C will swallow it.

– Alex B Aug 21 '09 at 0:14 Kind of cheating, in that it just prints them out. ;) – Noldorin Aug 21 '09 at 1:01 I realized that when it compiled and ran. That's awful.

You are a horrible person for doing this. (I always love it when C solutions beat Python and Perl. ) – Chris Lutz Aug 21 '09 at 1:02 @Noldorin: I think this code golf challenge was ill-specified with regards to I/O, use of libraries, etc.I'd say my solution meets the criteria , because it is by itself a complete program and output is formatted exactly according to the example.

– Alex B Aug 21 '09 at 1:22.

Mathematica (15 chars including brackets): FactorInteger Example: FactorInteger42 {{2, 1}, {3, 1}, {7, 1}}.

10 Now that's thinking about a problem in the right way. – peterb Aug 20 '09 at 11:45 2 That doesn't follow the example output: 2x11x11x17x439. You could just use bash factor x.

Whoohoo, 6 characters! I'm so leet!1! – Justin Aug 20 '09 at 14:40 @Justin: thanks, I didn't know about factor!

– Roberto Bonvallet Aug 20 '09 at 20:48.

Python: 86 chars with input and output d,s,n=2,'',int(raw_input()) while n>1: if n%d:d+=1 else:s+='%dx'%d;n/=d print s:-1.

Haskell, 56 chars: a%1= a%n|mod n a p 1806046 2,11,11,17,439.

Python (228 chars without I/O, 340 with): import sys def primeFactors(n): l = while n > 1: for I in xrange(2,n+1): if n % I == 0: l. Append(i) n = n // I break return l if len(l) > 0 else n n = int(sys. Argv1) print '%d: %s' % (n, 'x'.

Join(map(lambda x: str(x), primeFactors(n)))) Can be compressed to 120 chars: import sys n,l=int(sys. Argv1), while n>1: for I in range(2,n+1): if n%i==0:l+=str(i);n/=i;break print'x'. Join(l) Note: That's a tab character before the if, not four spaces.It works as another level of indentation and only costs one character instead of two.

It shouldn't be readable for code golf: the function should be called p(n) and there's an awful lot of spaces you could strip out of there. – paxdiablo Aug 20 '09 at 8:48 I'll start optimizing when someone comes up with something with less than 228 chars ;) – Aaron Digulla Aug 20 '09 at 9:01 You can trim this some more - swap l. Append(i) for l+=i and n=n//i for n/=i and you may as well swap xrange() for range() if we're counting characters.

– Dave Webb Aug 20 '09 at 12:15 And range would work fine in Python 3 (but may bomb for large n in python 2. X) – Stefan Kendall Aug 20 '09 at 21:15 Empty lists are false... return l if len(l)>0 elsen --> return l orn – Steve Losh Aug 20 '09 at 22:18.

GNU bc, 47 chars, including collecting input (need the GNU extensions for print, else and read): x=read();for(i=2;x>1;)if(x%i){i+=1}else{x/=i;i} If you really want the x characters in the output, it's 64 chars: x=read();for(i=2;x>1;)if(x%i){i+=1}else{x/=i;print i;if(x>1)"x"} Also, note that using bc allows this to process numbers of arbitrary length.

F# 81 chars let rec f n=if n=1 thenelse let a=2..n|>List. Find(fun x->n%x=0)in a::f(n/a) It's terribly inefficient, but since the aim is undoubtedly to write the shortest code possible, I've neglected that matter. Readable form (using #light syntax): let rec factorise n = if n = 1 then else let a = 2 .. n |> List.

Find (fun x -> n % x = 0) a :: factorise (n / a).

You can still shave off 4 chars by not using the forward pipe and compacting the divisor test: let rec f n=if n=1 thenelse let a=List. Find((%)n>>(=)0)2..nin a::f(n/a) – cfern Sep 7 '09 at 8:15 @cfern: Edit it in then. – badp Apr 18 '10 at 11:07.

Erlang, the core is 122 chars and 152 for the whole module: -module(pf). -export(f/1). F(N) -> f(N,2,).

F(1,_,L) -> lists:reverse(L); f(N,P,L) when N rem P == 0 -> f(N div P,P,P|L); f(N,P,L) -> f(N,P+1,L). To call from console: 70> string:join(integer_to_list(X) || X.

A Mathematica answer that actually produces the specified output: Print@@RiffleJoin@@ConstantArray@@@FactorIntegern,x 55 characters. Assumes n is the input number and x doesn't have a value assigned to it.

Best Perl answer yet - 70 characters, and no extra modules (unless you count special features of 5.10): perl -nE'sub f{($a)=@_;$a%$_||return$_,f($a/$_)for 2..$a}$,=x;say f$_' Doesn't work for 1 or 0, but works fine for everything else. If you don't like using say, or are using an earlier version of Perl, here's an 81 character version: perl -ne'sub f{($a)=@_;$a%$_||return$_,f($a/$_)for 2..$a;}$,=x;$/="\n";print f$.

I get an unrecognized switch error for Perl 5.8.8. Do I need a newer version of Perl? – Alex Reynolds Aug 20 '09 at 23:04 No, I forgot to change -E to -e.Sorry.Fixed.

– Chris Lutz Aug 20 '09 at 23:05 Very nice. A bit more efficiency would help it run faster on larger-factored numbers, but obviously that's not the object of the game. – Alex Reynolds Aug 20 '09 at 23:13 s/ or /||/ and save two more char – mob Sep 15 '09 at 20:06 and change $,="x" to $_=x for two more – mob Sep 15 '09 at 20:42.

The Go programming language, 100 characters: package main;func main(){n:=42;c:="x";for i:=2;n>1;i++{if n%i1; i++ { if n%i.

Wow, you guys aren't very good at optimizing. I can do it in Perl in 63 characters, or 79 if you insist on including a #! /usr/bin/perl at the top: use Math::Big::Factors; @f=factor_wheel($ARGV0,1); print @f; (Don't look at me that way.

Committed programmers are lazy programmers. ).

One might as well use the equivalent of a #define statement. :) – Alex Reynolds Aug 20 '09 at 12:21 4 If you measure using a pointless metric, you don't get to complain when you get pointless answers. One may as well ask how many lines of assembly are generated by the call to New() in your example, above.

– peterb Aug 20 '09 at 12:36 2 Someone missed the point of code golf... – Alex B Aug 20 '09 at 13:23.

While it's not my best work, here's me answer in Haskell, 83 characters. F n = s 2..n n s _ = s (p:z) n = p:s x | x.

Perl, 223 characters perl -ne'f($o=$_,2);sub f{($v,$f)=@_;$d=$v/$f;if(!($d-int($d))){print"$f ";if(!p($d)){print"$d ";return(0);}else{f($d,$f);}}else{while(p(++$f)){}f($v,$f);}}sub p{for($i=2;$i.

Can shorten $o=$_;f($o,2); to f($o=$_,2); – Chris Lutz Aug 20 '09 at 21:00 Shortened it. Thanks! – Alex Reynolds Aug 20 '09 at 23:14.

VB6/VBA - 190 chars Public Function P(N As Long) As String Dim I As Long, O As String Do While N > 1: For I = 2 To N If N Mod I = 0 Then O = O & " " & I: N = N / I: Exit For: End If: Next: Loop: P = O: End Function.

1: good one, this is just what I was going to try. :-) As written it works for VB.net also. One improvemnt you can make in VB/VB (not sure about vb.Net) is to remove the "O" string variable and just use the P function return string directly, this saves about 19(?) characters.

– RBarryYoung Aug 23 '09 at 17:41 I have a solution below that its 147 chars, by using some of the naughty features of VB/VBA – FinancialRadDeveloper Nov 5 '10 at 12:12.

Ruby 39B 71B (via STDIN) #! Ruby -nrmathn p$_. To_i.

Prime_division. Map{|d,c|d*c}.flatten. Join"x.

C# and LINQ, 241 Characters: public IEnumerable F(int n) { return Enumerable. Range(2,n-1) . Where(x => (n%x)==0 && F(x).Count()==1) .

Take(1) . SelectMany(x => new{x}. Concat(F(n/x))) .

DefaultIfEmpty(n); } public string Factor(int n) { return F(n). Aggregate("", (s,i) => s+"x"+i). TrimStart('x'); } Compressed: int F(int n){return Enumerable.

Range(2,n-1). Where(x=>(n%x)==0&&F(x). Length==1).

Take(1). SelectMany(x=>new{x}. Concat(F(n/x))).

DefaultIfEmpty(n).ToArray();}void G(int n){Console. WriteLine(F(n). Aggregate("",(s,i)=>s+"x"+i).

TrimStart('x'));}.

1 Your code produced a StackOverflowException for the number in the problem. I'm guessing it is because of the F(x).Count() statement. Kinda ironic.

– Yuriy Faktorovich Aug 20 '09 at 19:34 I tested the large version here (the one with .Count() vs . Length) without any issues.. – Jason Aug 20 '09 at 22:02.

C#, 366 characters C# is not the most averbose language for something like this, but this is quite compact: class P { static void Main(string a) { int I = int. Parse(a0); var p = new System.Collections.Generic.List(); for (int n = 2; I > 1; n++) if (p. Find(q => n % q == 0) == 0) { p.

Add(n); while (i % n == 0) { System.Console. WriteLine(n); I /= n; } } } } Edit: I saw that Noldorin used the List. Find method in his F# code, and realised that it would be a bit shorter than a foreach... Edit: Well, if it doesn't have to be a complete program... C#, 181 characters string f(int i) { var r = ""; var p = new System.Collections.Generic.List(); for (int n = 2; I > 1; n++) if (p.

Find(q => n % q == 0) == 0) { p. Add(n); while (i % n == 0) { r += "x" + n; I /= n; } } return r. Substring(1); } Compressed: string f(int i){var r="";var p=new System.Collections.Generic.List();for(int n=2;i>1;n++)if(p.

Find(q=>n%q==0)==0){p. Add(n);while(i%n==0){r+="x"+n;i/=n;}}return r. Substring(1);}.

In a similar vein as Paxinum (Mathematica answer), here's one in bash: $ factor 1806046 1806046: 2 11 11 17 439 7 characters the excluding number.

5 factor is not a shell builtin with any shell I have installed, rather, it's part of the standard BSD games distribution, and the source comes in at 5k+ characters. As it's not provided for by the shell itself, I'd argue your solution is not really done in any programming language. – Daniel Papasian Aug 20 '09 at 14:48 Yes, I have to agree.It was mostly a tongue-in-cheek answer.

– Johannes Hoff Aug 20 '09 at 15:09.

Python recursive solution 99 characters (including spaces) 87 characters (without spaces) def f(n,i=2,r=""): while n%i1 else r print f(input()):-1 Update: A completely recursive version def f(n,i=2,x=""): return x if n.

VB6/VBA - 147 chars I'm not allowed to leave comments , but it is possible to shorten the previous answer somewhat by not having Option Explicit. Taking advantage of some of the more dangerous features of VB6/VBA you can use the one below. No need to declare what the variable is and also the function doesn't need to be declared public either if going for ultimate shortness!

Also the End If is not needed if it is on the same line. Function P(N As Long) Dim I, O Do While N > 1: For I = 2 To N If N Mod I = 0 Then O = O & " " & I: N = N / I: Exit For: Next: Loop: P = O End Function This can be tested by : Public Sub TestP() Dim s: s = P(1806046) Debug. Print s End Sub.

I)) (exit f) )ifthen )do )loop )action I'm sure there's a much smaller APL program to do this.

74 75 Characters in Python a=input();b=2 while b*b.

I cant really gove you an answer,but what I can give you is a way to a solution, that is you have to find the anglde that you relate to or peaks your interest. A good paper is one that people get drawn into because it reaches them ln some way.As for me WW11 to me, I think of the holocaust and the effect it had on the survivors, their families and those who stood by and did nothing until it was too late.