# Find prime factors [duplicate]

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

• Should we make a function or a whole program? Any time constraints or limit to the input number? Commented Feb 7, 2011 at 20:43
• given number? from STDIN I presume? Commented Feb 7, 2011 at 21:00
• @dogbert yes, from STDIN Commented Feb 7, 2011 at 21:10
• Output format? Space-separated, comma-separaed, each factor on a line? Sorted? With exponents?
– Joey
Commented Feb 8, 2011 at 0:35
• space is fine for output, sorted wasn't specified and I wasn't thinking exponents would be used. just full number. Commented Feb 8, 2011 at 3:29

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

• 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?
– Nabb
Commented Feb 8, 2011 at 12:45
• @Nabb: what? are you suggesting bsdgames is non-standard? I even have them on my DS (using DSLinux). Commented Feb 8, 2011 at 20:51

## J - 2 characters

q:


Example:

   q: 31415
5 61 103


## dc, 48 chars

[ldp0<x]sp?2sd[[dsrld~0=p]dsxxcld1+sdlrd1<y]dsyx


# Ruby - 50494744 42 chars

2.upto(n=gets.to_i){|i|n/=p i while n%i<1}

• the () for n=gets.to_i are superfluous... Commented Feb 8, 2011 at 19:01
• @st0le, ah thanks, made the change. Commented Feb 8, 2011 at 19:11
• 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. Commented Feb 8, 2011 at 22:35
• Crossed out 44 is still 44
– user58826
Commented May 2, 2017 at 11:39

## Perl, 42 chars

map{$n/=$_,print$_,$/until$n%$_}2..($n=<>)  • Using say instead of print$_ let you save 4 chars. Commented Oct 28, 2013 at 0:20

## Windows PowerShell, 46

Naïve solution.

2..($x=+"$input")|%{for(;!($x%$_)){$_;$x/=$_}}  • 43 bytes: param($x)2..$x|%{for(;!($x%$_)){$_;$x/=$_}} Commented Aug 10, 2018 at 15:09
• The number is given on standard input. Read the task first, please.
– Joey
Commented Aug 11, 2018 at 5:52
• parm($x) is pure way to declare a standard input. Read the Powershell documentation first, please :) Commented Aug 11, 2018 at 6:43 • 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.
– Joey
Commented Aug 11, 2018 at 7:48
• 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 :) Commented Aug 11, 2018 at 15:38

## Python: 58

n=input()
for i in range(2,n+1):
while n%i<1:print i;n/=i

• how about n%i<1? Commented Feb 8, 2011 at 9:06

## Python (55)

based on marcog

n=input()
i=1
while~-n:
i+=1
while n%i<1:print i;n/=i


## 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  • *0 great idea! Commented Nov 3, 2013 at 14:48 ## Javascript (54) n=prompt()*1;for(i=2;n>1;n/=n%i?(++i,1):(alert(i),i));  • You can do prompt()*1 instead of parseInt(prompt()) to convert to an integer. Commented Feb 8, 2011 at 22:05 • +prompt() is shorter. Commented Sep 14, 2011 at 2:09 # Mathematica, 26 chars #&@@@FactorInteger@Input[]  ## 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);}  • 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. Commented Oct 28, 2013 at 5:42 • Good ideas! That brings it to 68. Commented Oct 28, 2013 at 16:33 ## 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 !. ## 100% Pure bash: 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
}

• 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 :). Commented Nov 3, 2013 at 13:22 • Even shorter: read p;for((i=2;p-1;));do((p%i&&++i))||{((p/=i));echo$i;};done (63 chars :)). Commented Nov 3, 2013 at 13:30
• Hi @gniourf_gniourf, thanks for declare -f, sometime, re-reading man pages... Bravo for your shortest bash solution, if you publish I will upvote! Commented Nov 3, 2013 at 13:58

## perl5.10: 36 chars

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


# Haskell 74 chars

s n=f((==0).mod n)[2..n]
f=filter


## Example

12 -> [2,3]
128 -> [2]
60 -> [2,3,5]


# Octave, 17 chars

factor(input(''))


# Scala, 111 bytes:

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)