current community

your communities

more stack exchange communities

company blog
Stack Exchange Inbox Reputation and Badges
tour help
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top
up vote 18 down vote favorite
2

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.

share|improve this question
    
Would've been much better if you disallowed built-ins. – TheBitByte 6 hours ago
    
@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 6 hours ago
    
Well then, enjoy the influx of <5 byte solutions! As I write this, Pyth already does it in 1 byte. – TheBitByte 6 hours ago
    
@TheBitByte Think of it as a language-by-language challenge, primarily. Try to beat Python's solution, or some other language without a builtin. – isaacg 4 hours ago
    
@isaacg Well, language-by-language is a better way of looking at it, I agree. – TheBitByte 4 hours ago

20 Answers 20

up vote 8 down vote

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!

share|improve this answer
    
I'd bet you've had this waiting for most of an hour... – ETHproductions yesterday
up vote 8 down vote

Pyth, 1 byte

P

I like Pyth's chances in this challenge.

share|improve this answer
9  
Until the "P" language comes along and does it in 0 bytes – downrep_nation 18 hours ago
up vote 4 down vote

Mathematica, 38 30 bytes

Thanks @MartinEnder for 8 bytes!

Join@@Table@@@FactorInteger@#&
share|improve this answer
up vote 3 down vote

MATL, 2 bytes

Yf

Try it online!

Obligatory "boring built-in answer".

share|improve this answer
up vote 3 down vote

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
share|improve this answer
up vote 2 down vote

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
share|improve this answer
up vote 2 down vote

J, 2 bytes

q:

Body must be at least 30 characters.

share|improve this answer
up vote 2 down vote

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)]
share|improve this answer
up vote 2 down vote

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.

share|improve this answer
up vote 2 down vote

Jelly, 2 bytes

Æf

Try it online!

share|improve this answer
up vote 1 down vote

Bash + coreutils, 19 bytes

factor|sed s/.*:.//

Try it online!

share|improve this answer
    
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. – Caleb 20 hours ago
    
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. – Dennis♦ 15 hours ago
up vote 1 down vote

MATLAB, 6 bytes

I think this does not require any explanation.

factor
share|improve this answer
up vote 1 down vote

Japt, 2 bytes

Uk

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

Test it online!

share|improve this answer
up vote 1 down vote

Cubix, 37 32 bytes

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

Try it online! or Watch it in action.

share|improve this answer
up vote 0 down vote

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
share|improve this answer
up vote 0 down vote

Pyke, 1 byte

P

Try it here!

Prime factors builtin.

share|improve this answer
up vote 0 down vote

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
}
share|improve this answer
up vote 0 down vote

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.

share|improve this answer
up vote 0 down vote

05AB1E, 1 byte

Ò

Try it online!

share|improve this answer
    
I wonder how many people will outgolf Dennis... – Erik the Outgolfer 7 hours ago
up vote 0 down vote

CJam, 2 bytes

mf

cjam.aditsu.net/...

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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