31
\$\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
  • 4
    \$\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

38 Answers 38

15
\$\begingroup\$

Pyth, 1 byte

P

I like Pyth's chances in this challenge.

\$\endgroup\$
1
  • 17
    \$\begingroup\$ Until the "P" language comes along and does it in 0 bytes \$\endgroup\$ Dec 26, 2016 at 13:03
14
\$\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
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\$
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\$
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\$
1
\$\begingroup\$

Vyxal, 1 byte

ǐ

Try it Online!

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

Vyxal, 16 bytes

ʀǎ:£$vǑ¥Zƛ÷w$ẋ;f

Try it Online at your own risk!

It is horrendously slow for large numbers, but it works

Explained

ʀǎ:£$vǑ¥Zƛ÷w$ẋ;f
ʀǎ                  # nth prime for each item in the range [0 ... input - 1]
  :£                # put that into the register while leaving it on the stack
    $vǑ             # get the divisbilty of each prime into the input
       ¥Z           # and zip that with the register
         ƛ    ;     # for each item in that zipped list: (each item is: [divisbilty, prime factor])
          ÷w        #      push divisbilty, [prime_factor]
            $ẋ      #      and repeat [prime_factor] divisibility times
               f    # flatten the unholy mess that results from doing the above
\$\endgroup\$
1
\$\begingroup\$

Japt, 1 byte

k

Try it online!

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

Haskell, 47 bytes

f 1=[]
f n=[k:f a|k<-[2..],a<-[1..n],a*k==n]!!0

Try it online!

f 1=[]
f n=[k:f(div n k)|k<-[2..],mod n k<1]!!0

Try it online!

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

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.