10
\$\begingroup\$

This question already has an answer here:

A whole program to find the prime factors of a given number. The number will be given on standard input.

\$\endgroup\$

marked as duplicate by hildred, Timtech, Hosch250, Justin, Darren Stone Jan 19 '14 at 8:13

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 1
    \$\begingroup\$ Should we make a function or a whole program? Any time constraints or limit to the input number? \$\endgroup\$ – Juan Feb 7 '11 at 20:43
  • \$\begingroup\$ updated description, thanks. \$\endgroup\$ – cbrulak Feb 7 '11 at 20:59
  • \$\begingroup\$ given number? from STDIN I presume? \$\endgroup\$ – Dogbert Feb 7 '11 at 21:00
  • 1
    \$\begingroup\$ Output format? Space-separated, comma-separaed, each factor on a line? Sorted? With exponents? \$\endgroup\$ – Joey Feb 8 '11 at 0:35
  • 1
    \$\begingroup\$ space is fine for output, sorted wasn't specified and I wasn't thinking exponents would be used. just full number. \$\endgroup\$ – cbrulak Feb 8 '11 at 3:29

18 Answers 18

6
\$\begingroup\$

Bash Shell

6 Chars

factor

If rot13 can be allowed, i don't see why this one is an issue...I'm sorry but this is very trivial.

\$\endgroup\$
  • 1
    \$\begingroup\$ You could argue that this one is more permissible than rot13, as this one is part of coreutils which is completely standard, and rot13 is part of... bsdgames? \$\endgroup\$ – Nabb Feb 8 '11 at 12:45
  • \$\begingroup\$ @Nabb: what? are you suggesting bsdgames is non-standard? I even have them on my DS (using DSLinux). \$\endgroup\$ – ninjalj Feb 8 '11 at 20:51
6
\$\begingroup\$

J - 2 characters

q:

Example:

   q: 31415
5 61 103
\$\endgroup\$
5
\$\begingroup\$

dc, 48 chars

[ldp0<x]sp?2sd[[dsrld~0=p]dsxxcld1+sdlrd1<y]dsyx
\$\endgroup\$
4
\$\begingroup\$

Ruby - 50 49 47 44 42 chars

2.upto(n=gets.to_i){|i|n/=p i while n%i<1}
\$\endgroup\$
  • \$\begingroup\$ the () for n=gets.to_i are superfluous... \$\endgroup\$ – st0le Feb 8 '11 at 19:01
  • \$\begingroup\$ @st0le, ah thanks, made the change. \$\endgroup\$ – Dogbert Feb 8 '11 at 19:11
  • \$\begingroup\$ In general, map is 1 character shorter than each. ;) But in this case, you can just use 2.upto(n=gets.to_i) to save 2 characters. \$\endgroup\$ – Ventero Feb 8 '11 at 22:35
  • \$\begingroup\$ @Ventero, updated, thanks! \$\endgroup\$ – Dogbert Feb 8 '11 at 23:08
  • \$\begingroup\$ Crossed out 44 is still 44 \$\endgroup\$ – programmer5000 May 2 '17 at 11:39
3
\$\begingroup\$

Perl, 42 chars

map{$n/=$_,print$_,$/until$n%$_}2..($n=<>)
\$\endgroup\$
  • \$\begingroup\$ Using say instead of print$_ let you save 4 chars. \$\endgroup\$ – F. Hauri Oct 28 '13 at 0:20
3
\$\begingroup\$

Windows PowerShell, 46

Naïve solution.

2..($x=+"$input")|%{for(;!($x%$_)){$_;$x/=$_}}
\$\endgroup\$
  • \$\begingroup\$ 43 bytes: param($x)2..$x|%{for(;!($x%$_)){$_;$x/=$_}} \$\endgroup\$ – mazzy Aug 10 '18 at 15:09
  • \$\begingroup\$ The number is given on standard input. Read the task first, please. \$\endgroup\$ – Joey Aug 11 '18 at 5:52
  • \$\begingroup\$ parm($x) is pure way to declare a standard input. Read the Powershell documentation first, please :) \$\endgroup\$ – mazzy Aug 11 '18 at 6:43
  • \$\begingroup\$ Try it out for yourself: echo 35 | powershell -noprofile -command "param($x)2..$x|%{for(;!($x%$_)){$_;$x/=$_}}". param declares a parameter to a function/script/scriptblock which is given after the invocation, not as pipeline input. Standard input is a well-defined term and refers to one of the default streams available to console programs on many platforms. \$\endgroup\$ – Joey Aug 11 '18 at 7:48
  • \$\begingroup\$ You don't need to run a PowerShell script as command from cmd.exe. Save the text to a file (test.ps1, for example) and run it from Powershell PS> test.ps1 35 :) \$\endgroup\$ – mazzy Aug 11 '18 at 15:38
3
\$\begingroup\$

Python: 58

n=input()
for i in range(2,n+1):
 while n%i<1:print i;n/=i
\$\endgroup\$
  • \$\begingroup\$ how about n%i<1? \$\endgroup\$ – st0le Feb 8 '11 at 9:06
2
\$\begingroup\$

Python (55)

based on marcog

n=input()
i=1
while~-n:
 i+=1
 while n%i<1:print i;n/=i
\$\endgroup\$
2
\$\begingroup\$

Pure Bash Solution (60 characters)

Based on F.Hauri's solution (thanks to him):

read p;for((i=2;p-1;));do((p%i++||(p/=--i)*0))||echo $i;done
\$\endgroup\$
  • \$\begingroup\$ *0 great idea! \$\endgroup\$ – F. Hauri Nov 3 '13 at 14:48
1
\$\begingroup\$

Javascript (54)

n=prompt()*1;for(i=2;n>1;n/=n%i?(++i,1):(alert(i),i));
\$\endgroup\$
  • 2
    \$\begingroup\$ You can do prompt()*1 instead of parseInt(prompt()) to convert to an integer. \$\endgroup\$ – HoLyVieR Feb 8 '11 at 22:05
  • 1
    \$\begingroup\$ +prompt() is shorter. \$\endgroup\$ – Casey Chu Sep 14 '11 at 2:09
1
\$\begingroup\$

Mathematica, 26 chars

#&@@@FactorInteger@Input[]
\$\endgroup\$
1
\$\begingroup\$

C (68)

Not the shortest, but I was curious to see how a C solution could compare.

d=2;main(n){scanf("%d",&n);for(;n>1;)n%d?++d:printf("%d\n",d,n/=d);}
\$\endgroup\$
  • 1
    \$\begingroup\$ Nice. You can also take advantage of the fact that printf accepts a variable number of arguments to hide the n/=d in its argument list. I suspect you could also save a character or two by promoting d to a global variable. \$\endgroup\$ – breadbox Oct 28 '13 at 5:42
  • \$\begingroup\$ Good ideas! That brings it to 68. \$\endgroup\$ – Daniel Lubarov Oct 28 '13 at 16:33
1
\$\begingroup\$

R, 72 characters

Just for the kicks, an attempt without using any preexisting function to prime-factorize:

n=scan(n=1);m=1:n;M=m[!n%%m&!m%in%c(1,n)];M[rowSums(!outer(M,M,`%%`))<2]

Ungolfed with explanations:

n <- scan(n=1) #Take one number from stdin
m <- 1:n
#Of which of the integers from 1 to n is n a multiple (excluding 1 and himself):
M <- m[!n%%m & !m%in%c(1,n)] 
#Trim that list by excluding integers that are multiples of others in the list:
M[rowSums(!outer(M,M,`%%`))<2]

NB: Instead of checking if n%%m==0, use the fact the 0 coerce as FALSE when using !.

\$\endgroup\$
1
\$\begingroup\$

100% Pure : 72 chars

read p;for((i=1;p>i++;));do while((p%i<1));do echo $i;((p/=i));done;done

or

read p;i=1;while((p>i++));do while((p%i<1));do o+=$i\ ;((p/=i));done;done ;echo $o

This seem longer, but in replacing for by while, I could make an overall loop and using alias to reduce then code:

alias D=done W=while
prime() { W read p;do i=1 o=;W((p>i++));do W((p%i<1));do o+=$i\ ;((p/=i));D;D;echo $o;D;}
unalias D W

This way, my (written) code whith the loop is 77 char length.

Anyway, the function is memorized with full command names:

declare -f prime
prime () 
{ 
    while read p; do
        i=1 o=;
        while ((p>i++)); do
            while ((p%i<1)); do
                o+=$i\ ;
                ((p/=i));
            done;
        done;
        echo $o;
    done
}
\$\endgroup\$
  • \$\begingroup\$ Hi @F.Hauri :). Here's a shorter version: read p;for((i=2;p-1;));do((p%i==0&&(p/=i)))&&echo $i||((++i));done. Also, use declare -f prime instead of the ugly set | sed. Cheers :). \$\endgroup\$ – gniourf_gniourf Nov 3 '13 at 13:22
  • \$\begingroup\$ Even shorter: read p;for((i=2;p-1;));do((p%i&&++i))||{((p/=i));echo $i;};done (63 chars :)). \$\endgroup\$ – gniourf_gniourf Nov 3 '13 at 13:30
  • \$\begingroup\$ Hi @gniourf_gniourf, thanks for declare -f, sometime, re-reading man pages... Bravo for your shortest bash solution, if you publish I will upvote! \$\endgroup\$ – F. Hauri Nov 3 '13 at 13:58
0
\$\begingroup\$

Scala 111:

def f(i:Int,c:Int=2):List[Int]=if(i==c)List(i)else
if(i%c==0)c::f(i/c,c)else f(i,c+1)
f(readInt).mkString(" ")
\$\endgroup\$
0
\$\begingroup\$

perl5.10: 36 chars

map{$p/=$_,say until$p%$_}2..($p=<>)
\$\endgroup\$
0
\$\begingroup\$

Haskell 74 chars

s n=f((==0).mod n)[2..n]
main=readLn>>=print.f((==1).length.s).s
f=filter

Example

12 -> [2,3]
128 -> [2]
60 -> [2,3,5]
\$\endgroup\$
0
\$\begingroup\$

Octave, 17 chars

factor(input(''))
\$\endgroup\$

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