# Recover the prime from the prime power

Definition: a prime power is a natural number that can be expressed in the form pn where p is a prime and n is a natural number.

Task: Given a prime power pn > 1, return the prime p.

Testcases:

input output
9     3
16    2
343   7
2687  2687
59049 3


Scoring: This is . Shortest answer in bytes wins.

• Can n be 1? Jun 20, 2018 at 10:41
• @user202729: In the 4th test-case n = 1. Jun 20, 2018 at 10:53
• Maybe it would have been more challenging to get the power part instead of the prime part. As it is, this is just "Get the lowest factor that isn't 1"
– Jo King
Jun 20, 2018 at 13:48

# 05AB1E, 1 byte

f


Try it online!

• Are you sure that a list (or [] around the number) is a valid output? Jun 20, 2018 at 11:10
• @EriktheOutgolfer: Relevant meta Jun 20, 2018 at 11:19
• Huh, didn't know about that, thanks. Jun 20, 2018 at 12:06
• For those wondering, f = push list of prime factors (no duplicates) Jun 20, 2018 at 13:08

# Shakespeare Programming Language, 209 207 bytes

T.Ajax,.Page,.Act I:.Scene I:.[Enter Ajax and Page]Ajax:Listen tothy!Page:You cat!Scene V:.Page:You be the sum ofyou a cat!Be the product ofthe quotient betweenI you you worse I?If soLet usScene V.Open heart


Try it online!

(I/you)*you<I is shorter than I%you>0 in SPL.

• The right tool for the job. Jun 20, 2018 at 20:09

# Java 8, 4639 37 bytes

n->{int r=1;for(;n%++r>0;);return r;}


-7 bytes indirectly thanks to @Tsathoggua.
-2 bytes thanks to JoKing

Try it online.

Explanation:

n->{               // Method with integer as both parameter and return-type
int r=1;         //  Start the result-integer r at 1
for(;n%++r>0;);  //  Increase r by 1 before every iteration with ++r
//  and loop until n is divisible by r
return r;}       //  After the loop, return r as result

• Following Luis Mendo's answer in python3, would it be possible to write n->{for(int i=1;++i<=n;)if(n%i<1)return i;} to get 43 characters? (I don't speak Java.) Jun 20, 2018 at 12:52
• @Tsathoggua As you have it right now not, since Java methods must always have a return. n->{for(int i=1;++i<=n;)if(n%i<1)return i;return n;} would work, but is unfortunately longer. Java can have a single return in infinite loops however, which does indeed save bytes, so thanks! n->{for(int i=1;;)if(n%++i<1)return i;}. Since i will become n eventually (like with the test case 2687) and n%n==0, the i<=n isn't required in this case. Jun 20, 2018 at 13:14
• How about 37 bytes. I'm not familiar enough with Java to see if any more can be golfed
– Jo King
Jun 20, 2018 at 13:30
• @JoKing I don't see anything to golf further, so thanks for the -2. Jun 20, 2018 at 14:06

# Python 3, 36 35 bytes

-1 byte thanks to mathmandan

f=lambda n,x=2:n%x and f(n,x+1)or x


Try it online!

Recursive function that finds the first factor larger than 1

• Nice. You can (usually) save a byte if you replace if/else with and/or. Like, f=lambda n,x=2:n%x and f(n,x+1)or x. Jun 20, 2018 at 16:51

# MATL, 4 3 bytes

Yfu


Try it online!

### Explanation:

       % Implicit input:      
Yf     % Prime factorization: [3 3 3 3 3 3 3 3 3 3]
u    % Unique elements:     
% Implicit output

• Very nice improvement! I would upvote again :-) Jun 20, 2018 at 12:54

# Whitespace, 8061 60 bytes

[S S T  T   N
_Push_-1][S S S N
_Push_0][T  N
S S N
_Create_Label_LOOP][S S S T N
_Push_1][T  S S T   _Subtract][S N
S _Duplicate][S S S N
_Push_0][T  T   T   _Retrieve][S N
T   _Swap][T    S T T   _Modulo][N
T   T   N
_If_0_Jump_to_Label_LOOP][S S T T   N
_Push_-1][T S S N
_Multiply][T    N
S T _Print_as_number]


-20 bytes thanks to @JoKing.

Letters S (space), T (tab), and N (new-line) added as highlighting only.
[..._some_action] added as explanation only.

Try it online (with raw spaces, tabs and new-lines only).

Explanation in pseudo-code:

Integer n = STDIN as integer
Integer i = -1
Start LOOP:
i = i - 1
if(n modulo-i is negative)
Go to next iteration of LOOP
else
i = i * -1
Print i
Exit with error: No exit defined


Example run: input = 9

Command   Explanation                    Stack        Heap     STDIN    STDOUT    STDERR

SSTTN     Push -1                        [-1]
SSSN      Push 0                         [-1,0]
TNTT      Read STDIN as integer          [-1]         {0:9}    9
NSSN      Create Label_LOOP              [-1]         {0:9}
SSSTN    Push 1                         [-1,1]       {0:9}
TSST     Subtract top two (-1-1)        [-2]         {0:9}
SNS      Duplicate top (-2)             [-2,-2]      {0:9}
SSSN     Push 0                         [-2,-2,0]    {0:9}
TTT      Retrieve                       [-2,-2,9]    {0:9}
SNT      Swap top two                   [-2,9,-2]    {0:9}
TSTT     Modulo top two (9%-2)          [-2,-1]      {0:9}

SSTTN    Push -1                        [-2,-1]      {0:9}
TSST     Subtract top two (-2-1)        [-3]         {0:9}
SNS      Duplicate top (-2)             [-3,-3]      {0:9}
SSSN     Push 0                         [-3,-3,0]    {0:9}
TTT      Retrieve                       [-3,-3,9]    {0:9}
SNT      Swap top two                   [-3,9,-3]    {0:9}
TSTT     Modulo top two (9%-3)          [-3,0]       {0:9}
SSTTN    Push -1                        [-3,-1]      {0:9}
TSSN     Multiply top two (-3*-1)                 {0:9}
TNST     Print as integer               []           {0:9}             3
error


Program stops with an error: No exit found.

• Do you need the i == n check? n%n would be 0 anyway
– Jo King
Jun 20, 2018 at 11:03
• @JoKing Ah, of course. Thanks, 19 bytes saved right there. :) Jun 20, 2018 at 11:07
• Could you only loop if not n%i and call the print afterwards?
– Jo King
Jun 20, 2018 at 11:12
• @JoKing I'm pretty sure not. Whitespace doesn't really have loops, it just has jumps to labels. The only three options I have is to: 1. jump to a certain label unconditionally; 2. jump to a certain label if the top of the stack is 0; 3. jump to a certain label if the top of the stack is negative. Unfortunately there isn't a "jump to label if positive" to continue the loop. I could accomplish this by multiplying by -1 before checking for negative, but I doubt that will be shorter. Jun 20, 2018 at 11:15
• Tried to do it with a negative modulus and ended up at <s>62</s>60 bytes (yay). Turns out you can't store at negative heap addresses (though 0 saved a couple of bytes)
– Jo King
Jun 20, 2018 at 12:35

# Octave, 16 bytes

@(x)factor(x)(1)


Try it online!

### Explanation:

@(x)              % Anonymous function taking x as input
factor(x)     % Prime factorization
(1)  % Get the first element


Or:

@(x)max(factor(x))  % the makeup of makeup artists

• +1 for max factor Jun 20, 2018 at 16:48

# JavaScript (ES6), 25 bytes

f=(n,k=2)=>n%k?f(n,k+1):k


Try it online!

# Funky, 30 bytes

n=>fori=2n>i i++if1>n%i breaki


Try it online!

• 0== can be 1> I think. Jun 20, 2018 at 9:09

# Pyth, 2 bytes

hP


Try it here!

# Jelly, 3 bytes

ÆfḢ


Try it online!

ÆfṪ, ÆfX could also be seriously competing functions.
ÆfQ could be a seriously competing full program.

# C (gcc), 28 bytes

f(k,p){for(p=1;k%++p;);k=p;}


Try it online!

# Forth (gforth), 34 bytes

: f 1 begin 1+ 2dup mod 0= until ;


Try it online!

### Explanation

1. Iterate integers starting from 2
2. Stop and return when you find one that divides n with no remainder

### Code Explanation

: f               \ Define a new word
1               \ place a 1 on the stack (to use as a counter/index)
begin           \ start indefinite loop
1+ 2dup       \ increment counter and duplicate counter and prime power
mod           \ calculate power % index
0= until        \ end the loop if modulus is 0 (no remainder)
;                 \ end word definition


# R, 32 26 bytes

@Giuseppe with different logic and a shorter solution:

(x=2:(n=scan()))[!n%%x]


Try it online!

Original:

numbers::primeFactors(scan())


Try it online!

This is obviously a much superior port of the 05AB1E solution.

# APL (Dyalog Extended), 7 2 bytes

⊃⍭


Try it online!

⍭ gives a list of factors, ⊃ gets the first of them.

# Regex (ECMAScript), 10 bytes

(xx+?)\1*$ Try it online! Works by finding the smallest prime factor. Takes its input in bijective unary, as a sequence of x characters in which the length represents the number. The output is returned in capture group 1.  # No anchor needed, since every input N>=2 returns an output (xx+?) # \1 = the smallest number >=2 for which: \1*$     # N-\1 is divisible by \1

• Wow. The things regex can do...
– user
Feb 12, 2021 at 18:02

# Vyxal 1, 1 byte

′


There was a builtin just for this.

• Try it Online! Apr 10, 2021 at 0:09
• @Lyxal Is that because of Vyxal 2? If so, I can label mine Vyxal 1 and you can post a separate answer.
– user
Apr 10, 2021 at 0:22
• no, it's the exact same program. turns out you don't need the h at the end. Apr 10, 2021 at 0:32
• it just looks different Apr 10, 2021 at 0:32
• The ′ gives all prime factors. The question only wants one (hence why I made it ′h). However, other answers seem to get away with printing all factors, so it's just ′ (or Ǐ) Apr 10, 2021 at 2:15

# Brachylog, 2 bytes

ḋh


Try it online!

### Explanation

ḋ       Prime decomposition


# J, 4 bytes

0{q:


Select { the first 0 of the prime factors q:

Try it online!

# Neim, 1 byte

𝐔


Try it online!

• U+1D414 is one character, but in UTF-8 and UTF-16 this is represented by 4 bytes. Jun 21, 2018 at 11:06
• @RuudHelderman Correct, but this isn't in UTF-8 nor UTF-16.
– Okx
Jun 21, 2018 at 14:28
• @RuudHelderman You may want to see Neim codepage. Jun 21, 2018 at 16:09
• @JungHwanMin Thanks; browsing Okx's earlier Neim submissions, I noticed my slightly ignorant reaction wasn't the first. Clever feature, but far from obvious; warrants explanation (as done here). Quoting code-golf tag info: "Unless the question is specified to be scored by characters, it is scored by bytes. If it doesn't specify a character encoding to use for scoring, answers which use Unicode code points outside 0 to 255 should state the encoding used." Jun 21, 2018 at 19:20
• @RuudHelderman per meta consensus, if an answer does not specify an encoding, it defaults to the language's default encoding. If that doesn't exist, then it is UTF-8. In this case, Neim has a defined default encoding, so it is assumed to be the encoding of the answer, without the answerer having to explain as such. Jun 21, 2018 at 22:06

f n=until((<1).mod n)(+1)2


Try it online!

# Mathematica, 17 bytes

Divisors[#][]&


The second smallest divisor.

# Husk, 2 bytes

←p


Try it online!

# ARBLE, 19 bytes

index(factors(a),1)


Try it online!

# Japt -g, 1 byte

k


Try it here

# PowerShell, 31 bytes

param($a)(2..$a|?{!($a%$_)})


Try it online!

Constructs a range from 2 to input $a, pulls out those elements where (?) the modulo operation % results in a zero !(...) (i.e., those that are divisors of $a), and then takes the smallest  one thereof. That's left on the pipeline, output is implicit.

# Perl 6, 22 bytes

{grep($_%%*,2..$_)}


Try it online!

Anonymous code block that filters the factors of the range of 2 to the input and returns the first one. I tried using ^\$ to save 2 bytes, but that didn't work in the case that the input was prime.

# Visual Basic .NET (.NET Framework v4.5), 123 71 bytes

-52 bytes thanks to @Jo King

Function A(n)
For i=n To 2 Step-1
A=If(n Mod i=0,i,A)
Next
End Function


Try it online!

Ungolfed:

Function A(input As Long) As Long
For i = input To 2 Step -1
A = If (input Mod i = 0, i, A)
Next
End Function


Explanation:

The i loop searches backwards from the first number, and finds all numbers that divide it evenly. Because we are going backwards, the smallest is stored in the vairable A.

VB gives you a free variable that matches your function name (in my case, A). At the end of the function execution, the value in that variable is returned (barring an explicit Return statement.

• You don't need the prime check at all. The smallest factor of a number (other than 1) is guaranteed to be a prime, otherwise there would be a smaller factor
– Jo King
Jun 20, 2018 at 13:54
• @JoKing D'oh! Of course, can't believe I missed that. Thanks! Jun 20, 2018 at 13:55

f y=[x|x<-[2..],mod y x<1]!!0


Try it online!

# Python 3, 4745 44 bytes

Inspired by Kevin Cruijssen's answer in Java.

2 3 bytes removed thanks to Jo King.

lambda n:[i+1for i in range(n)if n%-~i<1]


Try it online!

• You have an extra space before the if, and the condition can be <1
– Jo King
Jun 20, 2018 at 10:31
• You can save one byte by doing range(n) and incrementing i in place
– Jo King
Jun 20, 2018 at 23:04