1528

26
+22  Q:

## Code Golf: Prime Factors of a Number

What is the shortest way, by character count, to find prime factors in any number?

Example Input: ` 1806046 `

Example Output: ` 2x11x11x17x439 `

Example Calculator

A:

In PARLANSE, this would do the trick (252 chars):

``````(action (procedure natural)
(loop
(ifthen (== ? 1) (return))
(do f i 2 ? 1
(ifthen (== (modulo ? i) 0)
(print ?)
(= ? (/ ? i))
(exit f)
)ifthen
)do
)loop
)action
``````

I'm sure there's a much smaller APL program to do this.

+5  A:

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.argv)
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.argv),[]
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.
I'll start optimizing when someone comes up with something with less than 228 chars ;)
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.
And range would work fine in Python 3 (but may bomb for large n in python 2.x)
Empty lists are false... return l if len(l)>0 else[n] --> return l or[n]
Actually your "n+1" in the range will catch the number itself, so l will never be empty, right? return l
@Steve: Doesn't work with p(-1), p(0) or p(1). You could argue that the first two aren't important but p(1) should work. @iftrue: That's why I used xrange()
It does work with p(1). It prints nothing because 1 is not prime (it does not have exactly two distinct divisors): http://en.wikipedia.org/wiki/Prime_number
+1  A:

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(a);
var p = new System.Collections.Generic.List<int>();
for (int n = 2; i > 1; n++)
if (p.Find(q => n % q == 0) == 0) {
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<int>();
for (int n = 2; i > 1; n++)
if (p.Find(q => n % q == 0) == 0) {
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<int>();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);}
``````
+3  A:

## F#

81 chars

``````let rec f n=if n=1 then[]else 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 then[]else let a=List.find((%)n>>(=)0)[2..n]in a::f(n/a)
@cfern: Edit it in then.
+2  A:

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<=sqrt(\$_);\$i++){if(\$_%\$i==0){return(1);}}}'
``````
Can shorten `\$o=\$_;f(\$o,2);` to `f(\$o=\$_,2);`
Shortened it. Thanks!
+1  A:

C# and LINQ, 241 Characters:

``````public IEnumerable<int> 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'));}
``````
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.
I tested the large version here (the one with .Count() vs .Length) without any issues..
+9  A:

Mathematica (15 chars including brackets):

``````FactorInteger
``````

Example:

``````FactorInteger

{{2, 1}, {3, 1}, {7, 1}}
``````
Now _that's_ thinking about a problem in the right way.
That doesn't follow the example output: 2x11x11x17x439. You could just use bash `factor x`. Whoohoo, 6 characters! I'm so leet!!1!
@Justin: thanks, I didn't know about factor!
+2  A:

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(\$ARGV,1);
print @f;
``````

(Don't look at me that way. Committed programmers are lazy programmers.)

What happens when you expand factor_wheel()? One might as well use the equivalent of a #define statement. :)
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.
Someone missed the point of code golf...
+12  A:

ANSI C, 79 characters

``````main(d,i){for(d+=scanf("%d",&i);i>1;i%d?++d:printf("%d%c",d,(i/=d)>1?'x':10));}
``````
That doesn't look like any ANSI C I've ever seen. What kind of `main()` takes two `int`s as arguments?
Ah, and here is the trick: you can use 'char **argv' as an int, and C will swallow it.
Kind of cheating, in that it just prints them out. ;)
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.)
@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.
@Chris: thanks, sir. :)
I think it was specified pretty well when it said "Example Input:" and "Example Output", and the output had nice pretty formatting.
+1  A:

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.

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.
Yes, I have to agree. It was mostly a tongue-in-cheek answer.
+16  A:

``````q:
``````
`~.@q:` if you want unique factors, but yeah :)
the example in the question shows 11 as factor twice.
+18  A:

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 except it won't compile at all.
@Alex B I just tried it, works fine. Are you sure you declared the input x?
@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 Seems to me like this is just for fun, but if you want to take it that seriously and have that strict of a definition, thats your prerogative
@Yuriy that's the standard format for code golf and is a part of the challenge, nothing to do with "my prerogative".
+3  A:

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?
No, I forgot to change -E to -e. Sorry. Fixed.
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.
s/ or /||/ and save two more char
and change `\$,="x"` to `\$_=x` for two more
@mobrule - Thanks. If you want, you can edit it yourself. That's the point of community wiki.
+2  A:

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<-z, mod x p /= 0, mod n x == 0] n
``````

I'm sure there's more that could be done, but for now it's good.

Edit: Rearranged things to shave off a character, less efficient, but smaller.

+8  A:

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]
``````
+2  A:

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.
+7  A:

``````a%1=[]
a%n|mod n a<1=a:p(div n a)
|True=(a+1)%n
p=(2%)
``````

Example:

``````*Main> p 1806046
[2,11,11,17,439]
``````
+3  A:

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 <- pf:f(1806046)], "x").
"2x11x11x17x439"
``````
+2  A:

Ruby 39B 71B (via STDIN)

``````#!ruby -nrmathn
p\$_.to_i.prime_division.map{|d,c|[d]*c}.flatten.join"x"
``````
+3  A:

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.

+3  A:

A Mathematica answer that actually produces the specified output:

``````Print@@Riffle[Join@@ConstantArray@@@FactorInteger[n],x]
``````

55 characters. Assumes `n` is the input number and `x` doesn't have a value assigned to it.

+2  A:

Perl, 70 char

``````\$y=<>;for(\$i=2;\$i<=\$y;){next if\$y%\$i++;\$y/=--\$i;push@x,\$i}print@{\$,=x}
``````
+2  A:

Euphoria: 106 characters

``````procedure f(atom a)atom x=2
loop do
while remainder(a,x)do
x+=1
end while
?x
a/=x
until a=1
end procedure
``````
+1  A:

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
``````
+1  A:

Python recursive solution

99 characters (including spaces) 87 characters (without spaces)

``````def f(n,i=2,r=""):
while n%i<1:r+="%dx"%i;n/=i
return f(n,i+1,r)if n>1 else r
print f(input())[:-1]
``````

Update: A completely recursive version

``````def f(n,i=2,x=""): return x if n<2 else f(n,i+1,x)if n%i else f(n/i,i,x+'%dx'%i)
print f(input())[:-1]
``````

Both versions are prone to stack overflows for all but the smallest of inputs.

+2  A:

The Go programming language, 111 characters:

``````package main;func main(){n:=42;for i:=2;i<n+1;i++{if n%i==0{n/=i;if n>1{print(i,"x");i=1}else{print(i,"\n")}}}}
``````

My program, with the correct indentation:

``````package main

func main() {
n := 42 // or whichever input number you like
for i := 2; i < n+1; i++ {
if n%i ==0 {
n /= i
if n>1 {
print(i, "x")
i=1
} else {
print(i, "\n")
}
}
}
}
``````