Code Golf: Prime Factors of a Number

Question

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

Example Input: 1806046

Example Output: 2x11x11x17x439

Example Calculator

Answer 1

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.

Answer 2

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.

Answer 3

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

Answer 4

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)

Answer 5

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

Answer 6

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

Answer 7

Mathematica (15 chars including brackets):

FactorInteger

Example:

FactorInteger[42]

{{2, 1}, {3, 1}, {7, 1}}

Answer 8

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

Answer 9

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

Answer 10

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.

Answer 11

Obligatory J answer (2 characters):

q:

Answer 12

C#, 69

x is input number

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

Answer 13

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$_'

Answer 14

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.

Answer 15

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]

Answer 16

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

Answer 17

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]

Answer 18

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"

Answer 19

Ruby 39B 71B (via STDIN)

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

Answer 20

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.

Answer 21

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.

Answer 22

Perl, 70 char

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

Answer 23

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

Answer 24

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

Answer 25

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.

Answer 26

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