tags:

views:

1528

answers:

26

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.

Ira Baxter
+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
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
I'll start optimizing when someone comes up with something with less than 228 chars ;)
Aaron Digulla
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
And range would work fine in Python 3 (but may bomb for large n in python 2.x)
Stefan Kendall
Empty lists are false... return l if len(l)>0 else[n] --> return l or[n]
Steve Losh
Actually your "n+1" in the range will catch the number itself, so l will never be empty, right? return l
Steve Losh
@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
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
+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
+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
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
@cfern: Edit it in then.
badp
+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
Can shorten `$o=$_;f($o,2);` to `f($o=$_,2);`
Chris Lutz
Shortened it. Thanks!
Alex Reynolds
+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
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
I tested the large version here (the one with .Count() vs .Length) without any issues..
Jason
+9  A: 

Mathematica (15 chars including brackets):

FactorInteger

Example:

FactorInteger[42]

{{2, 1}, {3, 1}, {7, 1}}
Paxinum
Now _that's_ thinking about a problem in the right way.
peterb
That doesn't follow the example output: 2x11x11x17x439. You could just use bash `factor x`. Whoohoo, 6 characters! I'm so leet!!1!
Justin
@Justin: thanks, I didn't know about factor!
Roberto Bonvallet
+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
What happens when you expand factor_wheel()? One might as well use the equivalent of a #define statement. :)
Alex Reynolds
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
Someone missed the point of code golf...
Alex B
+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
That doesn't look like any ANSI C I've ever seen. What kind of `main()` takes two `int`s as arguments?
Chris Lutz
Ah, and here is the trick: you can use 'char **argv' as an int, and C will swallow it.
Alex B
Kind of cheating, in that it just prints them out. ;)
Noldorin
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
@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
@Chris: thanks, sir. :)
Alex B
I think it was specified pretty well when it said "Example Input:" and "Example Output", and the output had nice pretty formatting.
Chris Lutz
+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
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
Yes, I have to agree. It was mostly a tongue-in-cheek answer.
Johannes Hoff
+16  A: 

Obligatory J answer (2 characters):

q:
Jimmy
`[email protected]:` if you want unique factors, but yeah :)
ephemient
the example in the question shows 11 as factor twice.
Jimmy
+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
Very nice!!!!!!!!
Alex
@Alex except it won't compile at all.
Alex B
@Alex B I just tried it, works fine. Are you sure you declared the input x?
Yuriy Faktorovich
@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
@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
@Yuriy that's the standard format for code golf and is a part of the challenge, nothing to do with "my prerogative".
Alex B
+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
I get an unrecognized switch error for Perl 5.8.8. Do I need a newer version of Perl?
Alex Reynolds
No, I forgot to change -E to -e. Sorry. Fixed.
Chris Lutz
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
s/ or /||/ and save two more char
mobrule
and change `$,="x"` to `$_=x` for two more
mobrule
@mobrule - Thanks. If you want, you can edit it yourself. That's the point of community wiki.
Chris Lutz
+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
+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
+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
+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
+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
+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
+2  A: 

Ruby 39B 71B (via STDIN)

#!ruby -nrmathn
p$_.to_i.prime_division.map{|d,c|[d]*c}.flatten.join"x"
matyr
+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
+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
+2  A: 

Perl, 70 char

$y=<>;for($i=2;$i<=$y;){next if$y%$i++;$y/=--$i;[email protected],$i}[email protected]{$,=x}
mobrule
+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
+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
+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
+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