Find prime factors [duplicate]

Question

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

Community · Accepted Answer · 2017-04-13 12:39:10Z

6

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.

edited Apr 13 '17 at 12:39

Community♦

1

answered Feb 8 '11 at 6:12

st0le

2,06218 silver badges22 bronze badges

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

Add a comment |

MPelletier · Accepted Answer · 2011-02-09 03:00:15Z

6

J - 2 characters

q:

Example:

   q: 31415
5 61 103

answered Feb 9 '11 at 3:00

MPelletier

3001 silver badge7 bronze badges

Add a comment |

ninjalj · Accepted Answer · 2011-02-07 23:03:56Z

5

dc, 48 chars

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

answered Feb 7 '11 at 23:03

ninjalj

3,0861 gold badge17 silver badges20 bronze badges

Add a comment |

Dogbert · Accepted Answer · 2011-02-08 23:07:20Z

4

Ruby - 50 49 47 44 42 chars

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

edited Feb 8 '11 at 23:07

answered Feb 7 '11 at 20:59

Dogbert

9834 silver badges13 bronze badges

\$\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

Add a comment |

ninjalj · Accepted Answer · 2011-02-07 22:07:37Z

3

Perl, 42 chars

map{$n/=$_,print$_,$/until$n%$_}2..($n=<>)

answered Feb 7 '11 at 22:07

ninjalj

3,0861 gold badge17 silver badges20 bronze badges

\$\begingroup\$ Using say instead of print$_ let you save 4 chars. \$\endgroup\$ – F. Hauri Oct 28 '13 at 0:20

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

3

Windows PowerShell, 46

Naïve solution.

2..($x=+"$input")|%{for(;!($x%$_)){$_;$x/=$_}}

edited Jun 17 '20 at 9:04

Community♦

1

answered Feb 8 '11 at 0:42

Joey

12.5k1 gold badge40 silver badges70 bronze badges

\$\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

| Show 4 more comments

Community · Accepted Answer · 2020-06-17 09:04:33Z

3

Python: 58

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

edited Jun 17 '20 at 9:04

Community♦

1

answered Feb 7 '11 at 20:52

moinudin

11.2k7 gold badges29 silver badges40 bronze badges

\$\begingroup\$ how about n%i<1? \$\endgroup\$ – st0le Feb 8 '11 at 9:06

Add a comment |

recursive · Accepted Answer · 2011-02-11 18:46:38Z

2

Python (55)

based on marcog

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

answered Feb 11 '11 at 18:46

recursive

9,48917 silver badges33 bronze badges

Add a comment |

Community · Accepted Answer · 2017-04-13 12:39:03Z

2

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

edited Apr 13 '17 at 12:39

Community♦

1

answered Nov 3 '13 at 14:06

gniourf_gniourf

1415 bronze badges

\$\begingroup\$ *0 great idea! \$\endgroup\$ – F. Hauri Nov 3 '13 at 14:48

Add a comment |

aviraldg · Accepted Answer · 2011-02-09 01:57:32Z

1

Javascript (54)

n=prompt()*1;for(i=2;n>1;n/=n%i?(++i,1):(alert(i),i));

edited Feb 9 '11 at 1:57

answered Feb 8 '11 at 15:22

aviraldg

1992 silver badges5 bronze badges

2

\$\begingroup\$ You can do prompt()*1 instead of parseInt(prompt()) to convert to an integer. \$\endgroup\$ – HoLyVieR Feb 8 '11 at 22:05
2

\$\begingroup\$ +prompt() is shorter. \$\endgroup\$ – Casey Chu Sep 14 '11 at 2:09

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

1

Mathematica, 26 chars

#&@@@FactorInteger@Input[]

edited Jun 17 '20 at 9:04

Community♦

1

answered Oct 28 '13 at 6:59

alephalpha

24.5k5 gold badges39 silver badges101 bronze badges

Add a comment |

Daniel Lubarov · Accepted Answer · 2013-10-28 16:33:31Z

1

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);}

edited Oct 28 '13 at 16:33

answered Oct 27 '13 at 21:36

Daniel Lubarov

3211 silver badge9 bronze badges

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

Add a comment |

plannapus · Accepted Answer · 2013-10-29 09:26:50Z

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

F. Hauri · Accepted Answer · 2013-11-03 14:13:43Z

1

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
}

edited Nov 3 '13 at 14:13

answered Oct 28 '13 at 1:21

F. Hauri

2,86418 silver badges36 bronze badges

\$\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

Add a comment |

F. Hauri · Accepted Answer · 2013-10-28 01:08:23Z

0

perl5.10: 36 chars

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

edited Oct 28 '13 at 1:08

answered Oct 28 '13 at 0:08

F. Hauri

2,86418 silver badges36 bronze badges

Add a comment |

Ray · Accepted Answer · 2013-10-28 06:27:24Z

0

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]

answered Oct 28 '13 at 6:27

Ray

2,00610 silver badges17 bronze badges

Add a comment |

MrD · Accepted Answer · 2013-10-29 08:14:20Z

0

Octave, 17 chars

factor(input(''))

answered Oct 29 '13 at 8:14

MrD

1714 bronze badges

Add a comment |

pppery · Accepted Answer · 2020-06-17 14:48:11Z

0

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

edited Jun 17 '20 at 14:48

pppery

5,62321 silver badges37 bronze badges

answered Sep 4 '11 at 22:33

user unknown

4,45027 silver badges30 bronze badges

Add a comment |

Stack Exchange Network

current community

your communities

more stack exchange communities

Find prime factors [duplicate]

18 Answers 18

Bash Shell

J - 2 characters

dc, 48 chars

Ruby - 50 49 47 44 42 chars

Perl, 42 chars

Windows PowerShell, 46

Python: 58

Python (55)

Pure Bash Solution (60 characters)

Javascript (54)

Mathematica, 26 chars

C (68)

R, 72 characters

100% Pure bash: 72 chars

perl5.10: 36 chars

Haskell 74 chars

Example

Octave, 17 chars

Scala, 111 bytes:

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

Linked

Hot Network Questions

Find prime factors [duplicate]

18 Answers 18

Bash Shell

J - 2 characters

dc, 48 chars

Ruby - 50 49 47 44 42 chars

Perl, 42 chars

Windows PowerShell, 46

Python: 58

Python (55)

Pure Bash Solution (60 characters)

Javascript (54)

Mathematica, 26 chars

C (68)

R, 72 characters

100% Pure bash: 72 chars

perl5.10: 36 chars

Haskell 74 chars

Example

Octave, 17 chars

Scala, 111 bytes:

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

Linked

Related

Hot Network Questions