A whole program to find the prime factors of a given number. The number will be given on standard input.
-
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
Bash Shell
6 Charsfactor
If rot13
can be allowed, i don't see why this one is an issue...I'm sorry but this is very trivial.
-
1\$\begingroup\$ You could argue that this one is more permissible than
rot13
, as this one is part of coreutils which is completely standard, androt13
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
dc, 48 chars
[ldp0<x]sp?2sd[[dsrld~0=p]dsxxcld1+sdlrd1<y]dsyx
Ruby - 50 49 47 44 42 chars
2.upto(n=gets.to_i){|i|n/=p i while n%i<1}
-
-
-
\$\begingroup\$ In general,
map
is 1 character shorter thaneach
. ;) But in this case, you can just use2.upto(n=gets.to_i)
to save 2 characters. \$\endgroup\$ – Ventero Feb 8 '11 at 22:35 -
-
Perl, 42 chars
map{$n/=$_,print$_,$/until$n%$_}2..($n=<>)
-
\$\begingroup\$ Using
say
instead ofprint$_
let you save 4 chars. \$\endgroup\$ – F. Hauri Oct 28 '13 at 0:20
Windows PowerShell, 46
Naïve solution.
2..($x=+"$input")|%{for(;!($x%$_)){$_;$x/=$_}}
-
\$\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
Python: 58
n=input()
for i in range(2,n+1):
while n%i<1:print i;n/=i
Python (55)
based on marcog
n=input()
i=1
while~-n:
i+=1
while n%i<1:print i;n/=i
Javascript (54)
n=prompt()*1;for(i=2;n>1;n/=n%i?(++i,1):(alert(i),i));
-
2\$\begingroup\$ You can do
prompt()*1
instead ofparseInt(prompt())
to convert to an integer. \$\endgroup\$ – HoLyVieR Feb 8 '11 at 22:05 -
2
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);}
-
1\$\begingroup\$ Nice. You can also take advantage of the fact that
printf
accepts a variable number of arguments to hide then/=d
in its argument list. I suspect you could also save a character or two by promotingd
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
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
}
-
\$\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, usedeclare -f prime
instead of the uglyset | 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
perl5.10: 36 chars
map{$p/=$_,say until$p%$_}2..($p=<>)
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]
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)
f(readInt).mkString(" ")