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

Example Input: ` 1806046 `

Example Output: ` 2x11x11x17x439 `

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

Example Input: ` 1806046 `

Example Output: ` 2x11x11x17x439 `

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.

Ira Baxter
2009-08-20 08:28:24

+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[1])
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[1]),[]
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.

Aaron Digulla
2009-08-20 08:45:25

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
2009-08-20 08:48:42
I'll start optimizing when someone comes up with something with less than 228 chars ;)

Aaron Digulla
2009-08-20 09:01:57
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
2009-08-20 12:15:23
And range would work fine in Python 3 (but may bomb for large n in python 2.x)

Stefan Kendall
2009-08-20 21:15:34
Empty lists are false... return l if len(l)>0 else[n] --> return l or[n]

Steve Losh
2009-08-20 22:18:27
Actually your "n+1" in the range will catch the number itself, so l will never be empty, right? return l

Steve Losh
2009-08-20 22:21:53
@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()

Aaron Digulla
2009-08-21 06:50:29
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

Steve Losh
2009-08-21 11:53:40
+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[0]);
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) {
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) {
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<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);}
```

Guffa
2009-08-20 09:09:15

+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)
```

Noldorin
2009-08-20 09:17:44

+2
A:

**Perl, 223 characters**

```
perl -ne'f($o=$_,2);sub f{($v,$f)[email protected]_;$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($_[0]);$i++){if($_[0]%$i==0){return(1);}}}'
```

Alex Reynolds
2009-08-20 09:18:14

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

Jason
2009-08-20 11:12:32

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
2009-08-20 19:34:19
I tested the large version here (the one with .Count() vs .Length) without any issues..

Jason
2009-08-20 22:02:04
+9
A:

Mathematica (15 chars including brackets):

```
FactorInteger
```

Example:

```
FactorInteger[42]
{{2, 1}, {3, 1}, {7, 1}}
```

Paxinum
2009-08-20 11:41:27

That doesn't follow the example output: 2x11x11x17x439. You could just use bash `factor x`. Whoohoo, 6 characters! I'm so leet!!1!

Justin
2009-08-20 14:40:05
+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[0],1);
print @f;
```

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

peterb
2009-08-20 11:44:01

What happens when you expand factor_wheel()? One might as well use the equivalent of a #define statement. :)

Alex Reynolds
2009-08-20 12:21:59
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
2009-08-20 12:36:09
+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));}
```

Alex B
2009-08-20 13:39:39

That doesn't look like any ANSI C I've ever seen. What kind of `main()` takes two `int`s as arguments?

Chris Lutz
2009-08-20 20:46:34
Ah, and here is the trick: you can use 'char **argv' as an int, and C will swallow it.

Alex B
2009-08-21 00:14:56
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
2009-08-21 01:02:43
@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
2009-08-21 01:22:30
I think it was specified pretty well when it said "Example Input:" and "Example Output", and the output had nice pretty formatting.

Chris Lutz
2009-08-21 21:34:21
+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.

Johannes Hoff
2009-08-20 14:28:20

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
2009-08-20 14:48:54
+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":""));};
```

Yuriy Faktorovich
2009-08-20 19:15:26

@Alex B I just tried it, works fine. Are you sure you declared the input x?

Yuriy Faktorovich
2010-08-09 04:59:21
@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
2010-08-09 05:14:12
@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 Faktorovich
2010-08-09 12:51:20
@Yuriy that's the standard format for code golf and is a part of the challenge, nothing to do with "my prerogative".

Alex B
2010-08-09 23:41:36
+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)[email protected]_;$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)[email protected]_;$a%$_||return$_,f($a/$_)for 2..$a;}$,=x;$/="\n";print f$_'
```

Chris Lutz
2009-08-20 21:23:25

I get an unrecognized switch error for Perl 5.8.8. Do I need a newer version of Perl?

Alex Reynolds
2009-08-20 23:04:11
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
2009-08-20 23:13:28
@mobrule - Thanks. If you want, you can edit it yourself. That's the point of community wiki.

Chris Lutz
2009-09-16 02:33:37
+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.

ReaperUnreal
2009-08-20 21:33:14

+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]
```

Triptych
2009-08-20 21:35:33

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

DJ
2009-08-20 23:16:59

+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
2009-08-23 17:41:42
+7
A:

**Haskell, 56 chars:**

```
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]
```

sth
2009-08-21 00:54:25

+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"
```

zakovyrya
2009-08-21 04:58:09

+2
A:

**Ruby** ~~39B~~ 71B (via STDIN)

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

matyr
2009-08-23 17:04:10

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

Jon Bright
2009-08-30 13:58:26

+3
A:

A Mathematica answer that actually produces the specified output:

```
[email protected]@Riffle[[email protected]@[email protected]@@FactorInteger[n],x]
```

55 characters. Assumes `n`

is the input number and `x`

doesn't have a value assigned to it.

Pillsy
2009-09-15 19:08:22

+2
A:

Perl, 70 char

```
$y=<>;for($i=2;$i<=$y;){next if$y%$i++;$y/=--$i;[email protected],$i}[email protected]{$,=x}
```

mobrule
2009-09-15 20:01:17

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

Matt Lewis
2009-09-15 21:11:45

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

FinancialRadDeveloper
2010-02-10 10:16:53

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

MAK
2010-02-10 10:59:35

+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")
}
}
}
}
```

wok
2010-10-09 19:12:36