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.

@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. — ETHproductions
– ETHproductions, Commented Dec 27, 2016 at 0:29
Well then, enjoy the influx of <5 byte solutions! As I write this, Pyth already does it in 1 byte. — Buffer Over Read
– Buffer Over Read, Commented Dec 27, 2016 at 0:30
@TheBitByte Think of it as a language-by-language challenge, primarily. Try to beat Python's solution, or some other language without a builtin. — izzyg
– izzyg, Commented Dec 27, 2016 at 2:30
@isaacg Well, language-by-language is a better way of looking at it, I agree. — Buffer Over Read
– Buffer Over Read, Commented Dec 27, 2016 at 2:47

Dennis · Accepted Answer · 2016-12-26 04:01:39Z

15

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!

answered Dec 26, 2016 at 4:01

Dennis

212k41 gold badges380 silver badges830 bronze badges

1

\$\begingroup\$ I'd bet you've had this waiting for most of an hour... \$\endgroup\$

ETHproductions
– ETHproductions

2016-12-26 04:02:42 +00:00
Commented Dec 26, 2016 at 4:02

Add a comment |

izzyg · Accepted Answer · 2016-12-26 08:34:07Z

15

Pyth, 1 byte

I like Pyth's chances in this challenge.

answered Dec 26, 2016 at 8:34

izzyg

42.3k5 gold badges79 silver badges216 bronze badges

21

\$\begingroup\$ Until the "P" language comes along and does it in 0 bytes \$\endgroup\$

downrep_nation
– downrep_nation

2016-12-26 13:03:04 +00:00
Commented Dec 26, 2016 at 13:03

Add a comment |

xnor · Accepted Answer · 2016-12-26 11:41:24Z

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

Community · Accepted Answer · 2020-06-17 09:04:33Z

8

Mathematica, 38 30 bytes

Thanks @MartinEnder for 8 bytes!

Join@@Table@@@FactorInteger@#&

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Dec 26, 2016 at 4:14

JungHwan Min

14k3 gold badges24 silver badges73 bronze badges

\$\begingroup\$ How about FactorInteger[#][[All, 1]]&? 26 bytes \$\endgroup\$

David G. Stork
– David G. Stork

2019-03-19 04:40:26 +00:00
Commented 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\$

JungHwan Min
– JungHwan Min

2019-03-19 07:16:41 +00:00
Commented Mar 19, 2019 at 7:16

Add a comment |

Laikoni · Accepted Answer · 2018-02-23 00:11:38Z

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

Dennis · Accepted Answer · 2016-12-26 06:28:18Z

5

Jelly, 2 bytes

Æf

Try it online!

answered Dec 26, 2016 at 6:28

Dennis

212k41 gold badges380 silver badges830 bronze badges

Add a comment |

ETHproductions · Accepted Answer · 2016-12-26 04:27:13Z

4

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

edited Dec 26, 2016 at 4:27

answered Dec 26, 2016 at 4:06

ETHproductions

50.3k6 gold badges96 silver badges241 bronze badges

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

Spitemaster
– Spitemaster

2021-05-31 04:17:45 +00:00
Commented 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
– tsh

2021-05-31 06:17:01 +00:00
Commented May 31, 2021 at 6:17

Add a comment |

ETHproductions · Accepted Answer · 2016-12-27 04:01:46Z

4

Cubix, 37 32 bytes

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

Try it online! or Watch it in action.

edited Dec 27, 2016 at 4:01

answered Dec 27, 2016 at 0:18

ETHproductions

50.3k6 gold badges96 silver badges241 bronze badges

Add a comment |

flawr · Accepted Answer · 2021-06-01 22:54:01Z

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!

user45941 · Accepted Answer · 2016-12-26 04:03:53Z

3

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

answered Dec 26, 2016 at 4:03

user45941

\$\begingroup\$ You can probably just use o now, right? \$\endgroup\$

Oliver
– Oliver

2018-06-21 01:42:49 +00:00
Commented Jun 21, 2018 at 1:42
\$\begingroup\$ @Oliver Yes, but I don't usually update old answers with builtins. \$\endgroup\$

user45941
– user45941

2018-06-21 02:00:29 +00:00
Commented Jun 21, 2018 at 2:00

Add a comment |

alephalpha · Accepted Answer · 2016-12-26 04:26:02Z

3

J, 2 bytes

q:

~~Body must be at least 30 characters.~~

answered Dec 26, 2016 at 4:26

alephalpha

51.9k7 gold badges75 silver badges196 bronze badges

Add a comment |

DJMcMayhem · Accepted Answer · 2016-12-26 05:47:05Z

3

MATL, 2 bytes

Yf

Try it online!

Obligatory "boring built-in answer".

answered Dec 26, 2016 at 5:47

DJMcMayhem

60.1k18 gold badges203 silver badges352 bronze badges

Add a comment |

ETHproductions · Accepted Answer · 2016-12-26 16:26:03Z

3

Japt, 2 bytes

Uk

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

Test it online!

answered Dec 26, 2016 at 16:26

ETHproductions

50.3k6 gold badges96 silver badges241 bronze badges

Add a comment |

Dominic van Essen · Accepted Answer · 2021-07-01 16:58:26Z

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

lyxal · Accepted Answer · 2022-09-08 13:59:38Z

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

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.) — Deadcode
– Deadcode, Commented Sep 8, 2022 at 6:48
@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. — lyxal
– lyxal ♦, Commented Sep 8, 2022 at 7:17

Kade · Accepted Answer · 2016-12-26 06:09:57Z

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.

Community · Accepted Answer · 2020-06-17 09:04:33Z

2

MATLAB, 6 bytes

I think this does not require any explanation.

factor

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Dec 26, 2016 at 10:06

flawr

44.1k7 gold badges109 silver badges253 bronze badges

Add a comment |

Neil · Accepted Answer · 2016-12-26 11:23:26Z

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

Erik the Outgolfer · Accepted Answer · 2016-12-26 23:27:11Z

2

05AB1E, 1 byte

Ò

Try it online!

answered Dec 26, 2016 at 23:27

Erik the Outgolfer

40.8k5 gold badges46 silver badges125 bronze badges

1

\$\begingroup\$ I wonder how many people will outgolf Dennis... \$\endgroup\$

Erik the Outgolfer
– Erik the Outgolfer

2016-12-26 23:28:21 +00:00
Commented Dec 26, 2016 at 23:28

Add a comment |

mousetail · Accepted Answer · 2022-09-08 09:57:01Z

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;

Tbw · Accepted Answer · 2024-04-13 04:56:05Z

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.

Note to readers- this isn't some crazy magic, it's a special case — noodle person
– noodle person, Commented Apr 13, 2024 at 13:06

Dennis · Accepted Answer · 2016-12-26 05:56:54Z

1

Bash + coreutils, 19 bytes

factor|sed s/.*:.//

Try it online!

answered Dec 26, 2016 at 5:56

Dennis

212k41 gold badges380 silver badges830 bronze badges

\$\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
– Caleb

2016-12-26 10:17:56 +00:00
Commented 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
– Dennis

2016-12-26 16:01:30 +00:00
Commented Dec 26, 2016 at 16:01

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

1

Pyke, 1 byte

Try it here!

Prime factors builtin.

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Dec 26, 2016 at 13:29

Blue

28.8k8 gold badges53 silver badges101 bronze badges

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

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.

Community · Accepted Answer · 2020-06-17 09:04:33Z

1

CJam, 2 bytes

mf

cjam.aditsu.net/...

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

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Dec 26, 2016 at 23:39

Erik the Outgolfer

40.8k5 gold badges46 silver badges125 bronze badges

Add a comment |

Valentin Mariette · Accepted Answer · 2016-12-29 14:36:28Z

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

Pavel · Accepted Answer · 2017-01-07 07:01:43Z

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!

Refer to this gist to see how this submission can be golfed further: gist.github.com/kritixilithos/fde37dc5a8ae54852aa134a6e70ea495. If you need to clarify something, feel free to ping me at the 19th byte :) — user41805
– user41805, Commented Jan 7, 2017 at 10:34

Jörg Hülsermann · Accepted Answer · 2017-07-03 18:04:19Z

1

PHP, 51 bytes

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

Try it online!

edited Jul 3, 2017 at 18:04

answered Jun 10, 2017 at 17:37

Jörg Hülsermann

13.4k3 gold badges16 silver badges36 bronze badges

Add a comment |

gastropner · Accepted Answer · 2017-12-09 14:18:35Z

1

C (gcc), 51 bytes

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

Try it online!

answered Dec 9, 2017 at 14:18

gastropner

4,4831 gold badge17 silver badges20 bronze badges

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

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

Calculate the prime factors

Challenge

Rules

Test cases

Scoring

47 Answers 47

Python 2, 55 bytes

Pyth, 1 byte

Python 2, 53 bytes

Mathematica, 38 30 bytes

Haskell, 48 bytes

Jelly, 2 bytes

JavaScript (ES6), 44 bytes

Cubix, 37 32 bytes

Haskell, 47 bytes

Actually, 6 bytes

J, 2 bytes

MATL, 2 bytes

Japt, 2 bytes

R, 53 52 bytes

R, 59 58 bytes

Vyxal, 1 byte

Vyxal, 16 8 bytes

Explained

tone-deaf, 3 bytes

MATLAB, 6 bytes

Batch, 96 bytes

05AB1E, 1 byte

CellTail, 166 bytes

Explanation:

Uiua 0.11.0, 3 bytes SBCS

Bash + coreutils, 19 bytes

Pyke, 1 byte

Hexagony, 58 bytes

CJam, 2 bytes

C, 92 bytes

Java (OpenJDK), 259 bytes

PHP, 51 bytes

C (gcc), 51 bytes

Gol><>, 19 bytes

Explanation

Linked

Related

Hot Network Questions

Uiua 0.11.0, 3 bytes ^SBCS