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

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 2

Pyth, 1 byte

P

I like Pyth's chances in this challenge.

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

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 6

Jelly, 2 bytes

Æf

Try it online!

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

Haskell, 47 bytes

Basically this checks all integers 2, 3, 4, 5, ... for divisors of n. If we find one, we factor that out and repeat the process until we get to 1.

f 1=[]
f n=(:)<*>f.div n$until((<1).mod n)(+1)2

Try it online!

Answer 10

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 11

J, 2 bytes

q:

Body must be at least 30 characters.

Answer 12

MATL, 2 bytes

Yf

Try it online!

Obligatory "boring built-in answer".

Answer 13

Japt, 2 bytes

Uk

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

Test it online!

Answer 14

R, 53 52 bytes

p=function(n,i=2)if(n>1)c(i[m<-!n%%i],p(n/i^m,i+!m))

Try it online!

Recursive function: overflows the stack limit and errors on TIO for the last test case.

---

R, 59 58 bytes

function(n,i=2)while(n>1)if(n%%i)i=i+1 else{show(i);n=n/i}

Try it online!

Non-recursive function: does not error for large primes, but will still take a very long time to run (and so times-out without erroring on TIO for the last test case anyway).

Answer 15

Vyxal, 1 byte

ǐ

Try it Online!

Just the built-in. But that's boring, so

Vyxal, 16 8 bytes

K~æ~Ǒ$ẋf

Try it Online!

Explained

ʀ~æ~Ǒ$ẋf
ʀ~æ      # From the all numbers in the range [0, input], keep only those that are prime
   ~Ǒ    # Without popping anything, get the multiplicity of each prime divisor - this leaves the stack as [divisors, multiplicities]
     $ẋ  # Swap the two items and repeat each divisor multiplicity times
       f # Flatten and output that   

Answer 16

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 17

MATLAB, 6 bytes

I think this does not require any explanation.

factor

Answer 18

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 19

CellTail, 166 bytes

N,(u,u,_),N:1,(u,1),(0,2);(0,2),N,N:1,N,N;N,(u,v,0),N:1,(v,1),(u/v,2,(u/v)%2);N,(u,v,w),N:1,(u,v+1,u%(v+1)),N;a&(_,_,_),N,N:1,a,N;_,(v,1),_:1,v,N;N,u,N:1,(u,2,u%2),N;

Try the demo

Explanation:

Base case, when we reach the end switch to a recursion resistant tuple and pass a message right to break it. Then the message right sends a 1 to prevent recursion when the tuple has broken.

N,(u,u,_),N:1,(u,1),(0,2);(0,2),N,N:1,N,N;

We have found a factor, try again in the cell to the right with (u/v)

N,(u,v,0),N:1,(v,1),(u/v,2,(u/v)%2);

We have not found a factor, try another.

N,(u,v,w),N:1,(u,v+1,u%(v+1)),N;

Copy 3-tuples from left to current

a&(_,_,_),N,N:1,a,N;

Break recursion resistant tuples. Hopefully the next step the value from the right will throw a 1 to break the recursion.

_,(v,1),_:1,v,N;

Base case, start with trying 2 as a factor.

N,u,N:1,(u,2,u%2),N;

Answer 20

Uiua 0.11.0, 3 bytes ^SBCS

°/×

Try on Uiua Pad!

Takes \$n\$ and returns the prime factorization of \$n\$.

This is semantically funny, because it is literally "un-reduce-times", or undo the operation of multiplying the elements of a list together.

Answer 21

Bash + coreutils, 19 bytes

factor|sed s/.*:.//

Try it online!

Answer 22

Pyke, 1 byte

P

Try it here!

Prime factors builtin.

Answer 23

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 24

05AB1E, 1 byte

Ò

Try it online!

Answer 25

CJam, 2 bytes

mf

cjam.aditsu.net/...

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

Answer 26

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 27

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 28

PHP, 51 bytes

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

Try it online!

Answer 29

C (gcc), 51 bytes

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

Try it online!

Answer 30

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