27
\$\begingroup\$

We had a prime factorization challenge a while ago, but that challenge is nearly six years old and barely meets our current requirements, so I believe it's time for a new one.

Challenge

Write a program or function that takes as input an integer greater than 1 and outputs or returns a list of its prime factors.

Rules

  • Input and output may be given by any standard method and in any standard format.
  • Duplicate factors must be included in the output.
  • The output may be in any order.
  • The input will not be less than 2 or more than 231 - 1.
  • Built-ins are allowed, but including a non-builtin solution is encouraged.

Test cases

2 -> 2
3 -> 3
4 -> 2, 2
6 -> 2, 3
8 -> 2, 2, 2
12 -> 2, 2, 3
255 -> 3, 5, 17
256 -> 2, 2, 2, 2, 2, 2, 2, 2
1001 -> 7, 11, 13
223092870 -> 2, 3, 5, 7, 11, 13, 17, 19, 23
2147483646 -> 2, 3, 3, 7, 11, 31, 151, 331
2147483647 -> 2147483647

Scoring

This is , so the shortest code in bytes wins.

\$\endgroup\$
  • 2
    \$\begingroup\$ Would've been much better if you disallowed built-ins. \$\endgroup\$ – Buffer Over Read Dec 27 '16 at 0:25
  • 2
    \$\begingroup\$ @TheBitByte Challenges that disallow built-ins are generally looked down upon as Do X without Y challenges, especially since it's sometimes hard to tell whether a solution is technically a built-in. \$\endgroup\$ – ETHproductions Dec 27 '16 at 0:29
  • 1
    \$\begingroup\$ Well then, enjoy the influx of <5 byte solutions! As I write this, Pyth already does it in 1 byte. \$\endgroup\$ – Buffer Over Read Dec 27 '16 at 0:30
  • 2
    \$\begingroup\$ @TheBitByte Think of it as a language-by-language challenge, primarily. Try to beat Python's solution, or some other language without a builtin. \$\endgroup\$ – isaacg Dec 27 '16 at 2:30
  • 1
    \$\begingroup\$ @isaacg Well, language-by-language is a better way of looking at it, I agree. \$\endgroup\$ – Buffer Over Read Dec 27 '16 at 2:47

33 Answers 33

15
\$\begingroup\$

Pyth, 1 byte

P

I like Pyth's chances in this challenge.

\$\endgroup\$
  • 16
    \$\begingroup\$ Until the "P" language comes along and does it in 0 bytes \$\endgroup\$ – downrep_nation Dec 26 '16 at 13:03
13
\$\begingroup\$

Python 2, 55 bytes

f=lambda n,k=2:n/k*[0]and(f(n,k+1),[k]+f(n/k,k))[n%k<1]

Try it online!

\$\endgroup\$
  • 1
    \$\begingroup\$ I'd bet you've had this waiting for most of an hour... \$\endgroup\$ – ETHproductions Dec 26 '16 at 4:02
10
\$\begingroup\$

Python 2, 53 bytes

f=lambda n,i=2:n/i*[f]and[f(n,i+1),[i]+f(n/i)][n%i<1]

Tries each potential divisor i in turn. If i is a divisor, prepends it and restarts with n/i. Else, tries the next-highest divisor. Because divisors are checked in increasing order, only the prime ones are found.

As a program, for 55 bytes:

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

Mathematica, 38 30 bytes

Thanks @MartinEnder for 8 bytes!

Join@@Table@@@FactorInteger@#&
\$\endgroup\$
  • \$\begingroup\$ How about FactorInteger[#][[All, 1]]&? 26 bytes \$\endgroup\$ – David G. Stork Mar 19 at 4:40
  • \$\begingroup\$ @DavidG.Stork that wouldn't work because it would not repeat the prime factors if the power is greater than 1. \$\endgroup\$ – JungHwan Min Mar 19 at 7:16
5
\$\begingroup\$

Jelly, 2 bytes

Æf

Try it online!

\$\endgroup\$
5
\$\begingroup\$

Haskell, 48 bytes

(2%)
n%1=[]
n%m|mod m n<1=n:n%div m n|k<-n+1=k%m

Try it online! Example usage: (2%) 1001 yields [7,11,13].

\$\endgroup\$
4
\$\begingroup\$

JavaScript (ES6), 44 bytes

f=(n,x=2)=>n-1?n%x?f(n,x+1):[x,...f(n/x)]:[]

Horribly inefficient due to the fact that it iterates from 2 up to every prime factor, including the last. You can cut the time complexity dramatically at the cost of 5 bytes:

f=(n,x=2)=>x*x>n?[n]:n%x?f(n,x+1):[x,...f(n/x,x)]
\$\endgroup\$
4
\$\begingroup\$

Cubix, 37 32 bytes

vs(...<..1I>(!@)s)%?w;O,s(No;^;<

Try it online! or Watch it in action.

\$\endgroup\$
3
\$\begingroup\$

Actually, 6 bytes

w`in`M

Try it online!

Explanation:

w`in`M
w       factor into primes and exponents
 `in`M  repeat each prime # of times equal to exponent
\$\endgroup\$
  • \$\begingroup\$ You can probably just use o now, right? \$\endgroup\$ – Oliver Jun 21 '18 at 1:42
  • \$\begingroup\$ @Oliver Yes, but I don't usually update old answers with builtins. \$\endgroup\$ – Mego Jun 21 '18 at 2:00
3
\$\begingroup\$

J, 2 bytes

q:

Body must be at least 30 characters.

\$\endgroup\$
3
\$\begingroup\$

MATL, 2 bytes

Yf

Try it online!

Obligatory "boring built-in answer".

\$\endgroup\$
3
\$\begingroup\$

Japt, 2 bytes

Uk

A built-in k used on the input U. Also refers to a country.

Test it online!

\$\endgroup\$
2
\$\begingroup\$

tone-deaf, 3 bytes

This language is quite young and not really ready for anything major yet, but it can do prime factorization:

A/D

This will wait for user input, and then output the list of prime factors.

\$\endgroup\$
2
\$\begingroup\$

MATLAB, 6 bytes

I think this does not require any explanation.

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

Bash + coreutils, 19 bytes

factor|sed s/.*:.//

Try it online!

\$\endgroup\$
  • \$\begingroup\$ You can shave off a byte if whitespace doesn't matter in the output using factor|sed s/.*://. Also factor|cut -d: -f2 (or factor|cut -d\ -f2 to match your current output) is the same byte length but is going to run faster and use less memory overhead. \$\endgroup\$ – Caleb Dec 26 '16 at 10:17
  • \$\begingroup\$ I'll ask the OP about whitespace. Sadly, I'd need factor|cut -d\ -f2- to eliminate the leading space, which is one byte longer. \$\endgroup\$ – Dennis Dec 26 '16 at 16:01
1
\$\begingroup\$

Batch, 96 bytes

@set/an=%1,f=2,r=0
:l
@set/af+=!!r,r=n%%f
@if %r%==0 echo %f%&set/an/=f
@if %n% gtr 1 goto l
\$\endgroup\$
1
\$\begingroup\$

Pyke, 1 byte

P

Try it here!

Prime factors builtin.

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

Hexagony, 58 bytes

Not done golfing yet, but @MartinEnder should be able to destroy this anyway

Prints out factors space-separated, with a trailing space

Golfed:

2}\..}$?i6;>(<...=.\'/})."@...>%<..'':\}$"!>~\{=\)=\}&<.\\

Laid-out:

     2 } \ . .
    } $ ? i 6 ;
   > ( < . . . =
  . \ ' / } ) . "
 @ . . . > % < . .
  ' ' : \ } $ " !
   > ~ \ { = \ )
    = \ } & < .
     \ \ . . .

Explanation coming later.

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

05AB1E, 1 byte

Ò

Try it online!

\$\endgroup\$
  • 1
    \$\begingroup\$ I wonder how many people will outgolf Dennis... \$\endgroup\$ – Erik the Outgolfer Dec 26 '16 at 23:28
1
\$\begingroup\$

CJam, 2 bytes

mf

cjam.aditsu.net/...

This is a function. Martin, it seems I was sleepy.

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

C, 92 bytes

int p(int n){for(int i=2;i<n;i++)if(n%i==0)return printf("%d, ",i)+p(n/i);printf("%d\n",n);}

Ungolfed version:

#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>

int prime(int number) {
    for (int i = 2; i < number; i++) {
        if (number % i == 0) {
            printf("%d, ", i);
            return prime(number / i); //you can golf away a few bytes by returning the sum of your recursive function and the return of printf, which is an int
        }                             //this allow you to golf a few more bytes thanks to inline calls
    }
    printf("%d\n", number);
}

int main(int argc, char **argv) {
    prime(atoi(argv[1]));
}
\$\endgroup\$
1
\$\begingroup\$

Japt, 1 byte (non-competing)

k

Try it online!

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

PHP, 51 bytes

for($i=2;1<$a=&$argn;)$a%$i?$i++:$a/=$i*print"$i ";

Try it online!

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

C (gcc), 51 bytes

i;f(n){for(i=2;i<=n;)n%i?i++:printf("%d ",i,n/=i);}

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Perl 6,  77  64 bytes

{my$a=$_;.is-prime??$_!!map ->\f{|({$a%f||($a/=f)&&f}...^*!= f)},(2... *>$a)}

Try it

{my$a=$_;map ->\f{|({$a%f||($a div=f)&&f}...^ f>*)},(2... *>$a)}

Try it ( Note: it doesn't have enough time allotted to finish )


A much more performant version is slightly longer at 100 bytes.

{my$a=$_;map ->\f{|({$a.is-prime??($/=$a)&&($a=0)||$/!!($a%f||($a div=f)&&f)}...^ f>*)},(2... *>$a)}

Try it


Expanded: (64 byte version)

{
  my $a = $_;  # the input 「$_」 is read-only by default
  map
    -> \f {
      |(              # slip ( flattens into outer list )

        # generate sequence of 0 or more 「f」s
        {
          $a % f      # is it not evenly divisible

          ||          # if it is evenly divisible
          ($a div=f)  # divide it
          &&          # and
          f           # return 「f」
        }
        ...^   # keep doing that until
        f > *  # 「f」 is bigger
      )

    },

    # do that over the following list

    (2 ... * > $a) # generate a sequence from 2
                   # up to whatever the value of $a
                   # is at the time of the check
}
\$\endgroup\$
0
\$\begingroup\$

VB.NET, 86 bytes

Had this sitting around from some Project Euler programs. Removed the optimizations in the interest of shortness, and this is the result. Naturally, VB is very verbose, so it's fairly long. I'm not counting the leading whitespace. It can be omitted, but is easier to read with it.

This takes an integer as a parameter, and prints the prime factors with a comma after. There is a trailing comma at the end.

Sub A(a)
    For i=2To a ' VB re-evaluates a each time, so the /= at the end of the loop shortens this
        While a Mod i=0 ' this is a factor. We've grabbed primes before this, so this must be a prime factor
            Console.Write(i &",") ' output
            a/=i ' "mark" the prime as "used"
        End While
    Next
End Sub
\$\endgroup\$
0
\$\begingroup\$

Perl 6, 51 bytes

A recursive solution:

sub f(\n,\d=2){n-1??n%d??f n,d+1!!(d,|f n/d,d)!!()}
\$\endgroup\$
0
\$\begingroup\$

Java (OpenJDK), 259 bytes

import java.util.*;interface g{static void main(String[]z){int a=new Scanner(System.in).nextInt();int b=0;int[]l={};for(int i=2;i<=a;i++){for(;a%i<1;l[b-1]=i){l=Arrays.copyOf(l,b=l.length+1);a/=i;}}for(int i=0;i<b;i++)System.out.print(l[i]+(i<b-1?", ":""));}}

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Ruby, 61 bytes

require'prime';->x{x.prime_division.flat_map{|x|[x[0]]*x[1]}}

Shortest builtin-version I could think of.

\$\endgroup\$
0
\$\begingroup\$

Ruby, 48 bytes

->x{r,*c=2;0while(x%r<1?(x/=r)&&c<<r:x>=r+=1);c}

Try it online!

A little late to the party, but... why not?

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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