# 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? – Juan Feb 7 '11 at 20:43
• updated description, thanks. – cbrulak Feb 7 '11 at 20:59
• given number? from STDIN I presume? – Wile E. Coyote Feb 7 '11 at 21:00
• Output format? Space-separated, comma-separaed, each factor on a line? Sorted? With exponents? – Joey Feb 8 '11 at 0:35
• space is fine for output, sorted wasn't specified and I wasn't thinking exponents would be used. just full number. – cbrulak Feb 8 '11 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 Feb 8 '11 at 12:45
• @Nabb: what? are you suggesting bsdgames is non-standard? I even have them on my DS (using DSLinux). – ninjalj Feb 8 '11 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... – st0le Feb 8 '11 at 19:01
• @st0le, ah thanks, made the change. – Wile E. Coyote Feb 8 '11 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. – Ventero Feb 8 '11 at 22:35
• @Ventero, updated, thanks! – Wile E. Coyote Feb 8 '11 at 23:08
• Crossed out 44 is still 44 – programmer5000 May 2 '17 at 11:39

## Perl, 42 chars

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

## Windows PowerShell, 46

Naïve solution.

2..($x=+"$input")|%{for(;!($x%$_)){$_;$x/=$_}}  • 43 bytes: param($x)2..$x|%{for(;!($x%$_)){$_;$x/=$_}} – mazzy Aug 10 '18 at 15:09
• The number is given on standard input. Read the task first, please. – Joey Aug 11 '18 at 5:52
• parm($x) is pure way to declare a standard input. Read the Powershell documentation first, please :) – mazzy Aug 11 '18 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 Aug 11 '18 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 :) – mazzy Aug 11 '18 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? – st0le Feb 8 '11 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! – F. Hauri Nov 3 '13 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. – HoLyVieR Feb 8 '11 at 22:05 • +prompt() is shorter. – Casey Chu Sep 14 '11 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. – breadbox Oct 28 '13 at 5:42 • Good ideas! That brings it to 68. – Daniel Lubarov Oct 28 '13 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 ()
{
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 :). – gniourf_gniourf Nov 3 '13 at 13:22 • Even shorter: read p;for((i=2;p-1;));do((p%i&&++i))||{((p/=i));echo$i;};done (63 chars :)). – gniourf_gniourf Nov 3 '13 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! – F. Hauri Nov 3 '13 at 13:58

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


## perl5.10: 36 chars

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


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(''))