CodeGolf: Work out the prime factors of a given number

Question

Inspired by http://codegolf.com/prime-factors, try to solve this problem using the least number of keystrokes.

Sadly, you can only compete with Perl/PHP/Python/Ruby and I would love to see this problem solved in other not so traditional languages.

Answer 1

Perl

Just the function - returns a list of prime factors (49 significant* characters):

sub p {
  $p = $_[0];
  return if $p == 1;
  $p % $_ or return($_, p($p/$_)) for 2..$p;
}

Used to find primes of a constant (23 significant* characters):

$, = " ";
print p(10), "\n";

Used to find primes of a number from user input (28 significant* characters):

$, = " ";
print p(<STDIN>), "\n";

* "Significant" characters are non-whitespace as well as any whitespace that is needed for proper syntax. For anyone curious, significant whitespace is in bold. :P

Answer 2

Perl 107 98 characters

printf'%d: ',$n=<>;for($p=1;$n>=++$p;){for($i=0;0==$n%$p;$i++){$n/=$p}print$p,
$i>1?"^$i ":" "if$i}

that's

printf '%d: ', $n = <>;
for ($p = 1; $n >= ++$p;) {
  for ($i = 0;  0 == $n % $p;  $i++) {
    $n /= $p
  }
  print "$p", $i > 1 ? "^$i " : ' ' if $i
}

Answer 3

Haskell

I've started to learn Haskell recently - here's an attempt in that lesser known (but very nice) language.

main=readLn>>=print.f 2
f a 1=[]
f a x=if x`mod`a==0 then show a:f a(x`div`a)else f(a+1)x

89 characters, but cheating really because again the output format isn't right. I tried to correct the output but couldn't get it less than 208 chars:

import List
main=readLn>>=w
w n=putStrLn.foldl1(++).v n.map m.group.f 2$n
m a=' ':head a++j(length a)
v n=((s n++":"):)
s=show
j 1=[]
j n='^':s n
f a 1=[]
f a x=if x`mod`a==0 then s a:f a(x`div`a)else f(a+1)x

Any improvements welcomed. On a side note, I was amazed how much whitespace GHC lets you remove without complaining.

Answer 4

PowerShell, 146 161 chars

$i="$input"
"$i`: "+(
  $(
    for(;$i-gt1){
      for($x=1;++$x-le5e9){
        if(!($i%$x)){
          $i/=$x
          $x
          break
        }
      }
    }
  ) |
  sort |
  group |
  %{
    ''+$_.Name+('^'+$_.Count)*($_.Count-gt1)
  })

Almost ungolfed currently.

Answer 5

Python, 214 Characters

p=int(raw_input())
def r(x,d):d[x]=d.setdefault(x,0)+1;return d
y=lambda x,d:d==x and {x:1} or x%d and y(x,d+1) or r(d,y(x/d,2))
print "%d: %s"%(p," ".join([`x`+("^"+`c` if ~-c else "") for x,c in y(p,2).items()]))

My first code golf, don't judge. Probably a lot of optimization that could be done.

On the upside, it formats properly.