28
votes

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

Example Input: 1806046

Example Output: 2x11x11x17x439

Example Calculator

2
  • 1
    I assume that by "any number" you mean a number that can fit in a reasonably sized variable, and not for example 1093860897630819876058726938274695238746598327465982374659827346598763...
    – Guffa
    Aug 20, 2009 at 13:31
  • 2
    Guffa, my bc solution will process that number - I just don't know if it'll do so before the heat death of the universe.
    – Jon Bright
    Oct 8, 2009 at 19:14

30 Answers 30

22
votes

C#, 69

x is input number

int i=2;while(x>1)if(x%i++==0){x/=--i;Console.Write(i+(x>1?"x":""));};

With includes:

using system;
namespace nameSP
{
   class Program
   {
     static void Main(string[] args)
     { 
        int i=2;while(x>1)if(x%i++==0){x/=--i;Console.Write(i+(x>1?"x":""));};
     }
   }
}
5
  • 2
    @Alex except it won't compile at all.
    – Alex B
    Aug 9, 2010 at 4:23
  • @Alex B I just tried it, works fine. Are you sure you declared the input x? Aug 9, 2010 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, 2010 at 5:14
  • @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 Aug 9, 2010 at 12:51
  • 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, 2010 at 23:41
20
votes

Obligatory J answer (2 characters):

q:
2
  • 1
    ~.@q: if you want unique factors, but yeah :)
    – ephemient
    Aug 20, 2009 at 17:01
  • 6
    the example in the question shows 11 as factor twice.
    – Jimmy
    Aug 20, 2009 at 17:02
15
votes

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));}
6
  • 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, 2009 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, 2009 at 0:14
  • Kind of cheating, in that it just prints them out. ;)
    – Noldorin
    Aug 21, 2009 at 1:01
  • 2
    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, 2009 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, 2009 at 1:22
11
votes

Mathematica (15 chars including brackets):

FactorInteger

Example:

FactorInteger[42]

{{2, 1}, {3, 1}, {7, 1}}
3
  • 10
    Now that's thinking about a problem in the right way.
    – peterb
    Aug 20, 2009 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, 2009 at 14:40
  • 1
    @Justin: thanks, I didn't know about factor! Aug 20, 2009 at 20:48
10
votes

Python: 77 chars with input and output

d,s,n=2,'',input()
while n>1:
 if n%d:d+=1
 else:s+='%dx'%d;n/=d
print s[:-1]
10
votes

Haskell, 53 chars: (including 3 newlines)

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

Example:

*Main> p 1806046
[2,11,11,17,439]
6
votes

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.

8
  • 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, 2009 at 8:48
  • I'll start optimizing when someone comes up with something with less than 228 chars ;) Aug 20, 2009 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.
    – David Webb
    Aug 20, 2009 at 12:15
  • And range would work fine in Python 3 (but may bomb for large n in python 2.x) Aug 20, 2009 at 21:15
  • Empty lists are false... return l if len(l)>0 else[n] --> return l or[n]
    – Steve Losh
    Aug 20, 2009 at 22:18
5
votes

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)
2
  • 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
    Sep 7, 2009 at 8:15
  • @cfern: Edit it in then.
    – badp
    Apr 18, 2010 at 11:07
5
votes

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.

5
votes

11 characters in APL

Excluding function header and newlines

factors←{2÷/∪⌽∧\⍵∨⍳⍵}
1
4
votes

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"
4
votes

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.

4
votes

Ruby 39B 71B (via STDIN)

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

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$_'
6
  • I get an unrecognized switch error for Perl 5.8.8. Do I need a newer version of Perl? Aug 20, 2009 at 23:04
  • No, I forgot to change -E to -e. Sorry. Fixed.
    – Chris Lutz
    Aug 20, 2009 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. Aug 20, 2009 at 23:13
  • s/ or /||/ and save two more char
    – mob
    Sep 15, 2009 at 20:06
  • and change $,="x" to $_=x for two more
    – mob
    Sep 15, 2009 at 20:42
2
votes

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

3
  • 2
    What happens when you expand factor_wheel()? One might as well use the equivalent of a #define statement. :) Aug 20, 2009 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, 2009 at 12:36
  • 2
    Someone missed the point of code golf...
    – Alex B
    Aug 20, 2009 at 13:23
2
votes

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.

2
votes

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($_[0]);$i++){if($_[0]%$i==0){return(1);}}}'
1
  • Can shorten $o=$_;f($o,2); to f($o=$_,2);
    – Chris Lutz
    Aug 20, 2009 at 21:00
2
votes

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
2
  • +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. Aug 23, 2009 at 17:41
  • I have a solution below that its 147 chars, by using some of the naughty features of VB/VBA Nov 5, 2010 at 12:12
2
votes

Perl, 70 char

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

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
2
votes

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
0
2
votes

The Go programming language, 100 characters:

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

My program, with the correct indentation:

package main

func main() {
 n := 42 // or whichever input number you like
 c := "x" // separating printed integers
 for i:=2 ; n>1; i++ {
  if n%i<1 { // n%i==0
   n /= i
   if(n<2) { c = "" } // n==1
   print(i, c)
   i--
  }
 }
}
2
votes

74 75 Characters in Python

a=input();b=2
while b*b<=a:
    if a%b==0:print b;a/=b;b=1
    b+=1
print a

Derived from my TI-BASIC code for prime factorization.

Since I'm talking about TI-Basic...

77 Characters in TI-Basic

input a
2→b
while b²<a
a/b→c
if int(c)=c:then:disp b:c→a:1→b:end
b+1→b
end
disp a
1
vote

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'));}
2
  • 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. Aug 20, 2009 at 19:34
  • I tested the large version here (the one with .Count() vs .Length) without any issues..
    – Jason
    Aug 20, 2009 at 22:02
1
vote

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);}
1
vote

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.

3
  • 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. Aug 20, 2009 at 14:48
  • Yes, I have to agree. It was mostly a tongue-in-cheek answer. Aug 20, 2009 at 15:09
  • This helped me. thank you. On Mac OS X I used brew install coreutils then gfactor
    – jchook
    Mar 17, 2014 at 23:57
1
vote

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.

0
votes

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.

0
votes

Javascript, 56

f="";
for(i=2;i<n;i++)
    if(n%i==0){
        f+=i+"x";
        n/=i;i--
    }
f+=n;

(54 characters)

first declare n= the number to be factored (2 characters included)

then execute the code.

example:

> n=12345
  12345

> f="";for(i=2;i<n;i++)if(n%i==0){f+=i+"x";n/=i;i--}f+=n
  "3x5x823"
1
  • btw semicolons are technically optional in javascript
    – jchook
    Mar 17, 2014 at 23:55
0
votes

Python 3 163

Without printing the result.

l,f,p=len,lambda n:list(filter(lambda b:n%b==0,range(2,n))),lambda n:l(f(n))==0;r=lambda n: n if p(n) else[x if p(x) else r(x) for x in [f(n)[0],f(n)[l(f(n))-1]]]

Use it as a function:

print(r(1806046))

Not the answer you're looking for? Browse other questions tagged or ask your own question.