34
\$\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\$
12
  • 2
    \$\begingroup\$ Would've been much better if you disallowed built-ins. \$\endgroup\$ Dec 27, 2016 at 0:25
  • 6
    \$\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\$ Dec 27, 2016 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\$ Dec 27, 2016 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, 2016 at 2:30
  • 1
    \$\begingroup\$ @isaacg Well, language-by-language is a better way of looking at it, I agree. \$\endgroup\$ Dec 27, 2016 at 2:47

46 Answers 46

15
\$\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
  • 1
    \$\begingroup\$ I'd bet you've had this waiting for most of an hour... \$\endgroup\$ Dec 26, 2016 at 4:02
15
\$\begingroup\$

Pyth, 1 byte

P

I like Pyth's chances in this challenge.

\$\endgroup\$
1
  • 21
    \$\begingroup\$ Until the "P" language comes along and does it in 0 bytes \$\endgroup\$ Dec 26, 2016 at 13:03
11
\$\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\$
2
  • \$\begingroup\$ How about FactorInteger[#][[All, 1]]&? 26 bytes \$\endgroup\$ Mar 19, 2019 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\$ Mar 19, 2019 at 7:16
6
\$\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\$
5
\$\begingroup\$

Jelly, 2 bytes

Æf

Try it online!

\$\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\$
2
  • \$\begingroup\$ You can save a byte by outputting a string rather than an array: f=(n,i=2)=>n%i?n-1?f(n,i+1):"":i+" "+f(n/i) \$\endgroup\$ May 31, 2021 at 4:17
  • \$\begingroup\$ @Spitemaster Another byte (use comma): f=(n,i=2)=>n%i?f(n,i+1):n-i?i+[,f(n/i)]:i \$\endgroup\$
    – tsh
    May 31, 2021 at 6:17
4
\$\begingroup\$

Cubix, 37 32 bytes

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

Try it online! or Watch it in action.

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

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!

\$\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\$
2
  • \$\begingroup\$ You can probably just use o now, right? \$\endgroup\$
    – Oliver
    Jun 21, 2018 at 1:42
  • \$\begingroup\$ @Oliver Yes, but I don't usually update old answers with builtins. \$\endgroup\$
    – user45941
    Jun 21, 2018 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\$
3
\$\begingroup\$

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   
\$\endgroup\$
2
  • \$\begingroup\$ I think you should keep the 16 byte version too, since that doesn't even use any built-ins for enumerating divisors. (Though maybe there's something between 8 and 16 bytes that also fits that criterion.) \$\endgroup\$
    – Deadcode
    Sep 8, 2022 at 6:48
  • \$\begingroup\$ @Deadcode I'll be honest, i only removed it because I didn't think it would work anymore - it was written a very long time ago and many things have changed since. But turns out it still works in older versions, so I'll put it back a little later. \$\endgroup\$
    – lyxal
    Sep 8, 2022 at 7:17
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\$
0
2
\$\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\$
2
\$\begingroup\$

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

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

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;
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Note to readers- this isn't some crazy magic, it's a special case \$\endgroup\$
    – noodle man
    2 hours ago
1
\$\begingroup\$

Bash + coreutils, 19 bytes

factor|sed s/.*:.//

Try it online!

\$\endgroup\$
2
  • \$\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, 2016 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, 2016 at 16:01
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
  • 1
    \$\begingroup\$ I wonder how many people will outgolf Dennis... \$\endgroup\$ Dec 26, 2016 at 23:28
1
\$\begingroup\$

CJam, 2 bytes

mf

cjam.aditsu.net/...

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

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

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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