Calculate the prime factors

Question

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 2³¹ - 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 code-golf, so the shortest code in bytes wins.

Answer 1

Pyth, 1 byte

P

I like Pyth's chances in this challenge.

Answer 2

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!

Answer 3

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

Answer 4

Mathematica, 38 30 bytes

Thanks @MartinEnder for 8 bytes!

Join@@Table@@@FactorInteger@#&

Answer 5

Jelly, 2 bytes

Æf

Try it online!

Answer 6

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

Answer 7

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

Answer 8

Cubix, 37 32 bytes

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

Try it online! or Watch it in action.

Answer 9

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

Answer 10

J, 2 bytes

q:

Body must be at least 30 characters.

Answer 11

MATL, 2 bytes

Yf

Try it online!

Obligatory "boring built-in answer".

Answer 12

Japt, 2 bytes

Uk

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

Test it online!

Answer 13

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.

Answer 14

MATLAB, 6 bytes

I think this does not require any explanation.

factor

Answer 15

Bash + coreutils, 19 bytes

factor|sed s/.*:.//

Try it online!

Answer 16

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

Answer 17

Pyke, 1 byte

P

Try it here!

Prime factors builtin.

Answer 18

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.

Answer 19

05AB1E, 1 byte

Ò

Try it online!

Answer 20

CJam, 2 bytes

mf

cjam.aditsu.net/...

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

Answer 21

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

Answer 22

Japt, 1 byte (non-competing)

k

Try it online!

Answer 23

PHP, 51 bytes

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

Try it online!

Answer 24

C (gcc), 51 bytes

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

Try it online!

Answer 25

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
}

Answer 26

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

Answer 27

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)!!()}

Answer 28

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!

Answer 29

Ruby, 61 bytes

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

Shortest builtin-version I could think of.

Answer 30

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?

Answer 31

Pyt, 1 byte

ḋ

Boring built-in answer

Try it online!

Answer 32

Gol><>, 19 bytes

IT1WP2K%ZB|:N,:M?t;

Try it online!

Explanation

IT                  < [n]     read input to n then mark cell (T)
  1WP     |         < [n m=2] from 2 onwards (m=1;while m:m++;)
     2K%ZB          < [n m+1] copy two elements, mod, break if n%m==0
           :N       < [n m] (< where n%m==0) print m with newline
             ,:M?t; < [n/m] (< new n)        divide, if not 1 redo from T else exit

Answer 33

APL(NARS), 1 char, 2 bytes

π

That is...