# 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? – user202729 Jun 20 '18 at 10:41
• @user202729: In the 4th test-case n = 1. – Emigna Jun 20 '18 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 '18 at 13:48

# 05AB1E, 1 byte

f


Try it online!

# 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. – Jeremy Weirich Jun 20 '18 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.) – Tsathoggua Jun 20 '18 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. – Kevin Cruijssen Jun 20 '18 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 '18 at 13:30
• @JoKing I don't see anything to golf further, so thanks for the -2. – Kevin Cruijssen Jun 20 '18 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. – mathmandan Jun 20 '18 at 16:51

# MATL, 4 3 bytes

Yfu


Try it online!

### Explanation:

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

• Very nice improvement! I would upvote again :-) – Luis Mendo Jun 20 '18 at 12:54

# Whitespace, 8061 60 bytes

[S S T  T   N
_Push_-1][S S S N
_Push_0][T  N
T   T   _Read_STDIN_as_number][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}
NTSN     If neg.: Jump to Label_LOOP    [-2]         {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}
NTSN     If neg.: Jump to Label_LOOP    [-3]         {0:9}
SSTTN    Push -1                        [-3,-1]      {0:9}
TSSN     Multiply top two (-3*-1)       [3]          {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 '18 at 11:03
• @JoKing Ah, of course. Thanks, 19 bytes saved right there. :) – Kevin Cruijssen Jun 20 '18 at 11:07
• Could you only loop if not n%i and call the print afterwards? – Jo King Jun 20 '18 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. – Kevin Cruijssen Jun 20 '18 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 '18 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 – Brain Guider Jun 20 '18 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. – Kevin Cruijssen Jun 20 '18 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][1]


Try it online!

Original:

numbers::primeFactors(scan())[1]


Try it online!

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

# Vyxal, 1 byte

′


Try it online!

There's a builtin just for this.

# 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 at 18:02

# Brachylog, 2 bytes

ḋh


Try it online!

### Explanation

ḋ       Prime decomposition
h      Head


# 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. – Ruud Helderman Jun 21 '18 at 11:06
• @RuudHelderman Correct, but this isn't in UTF-8 nor UTF-16. – Okx Jun 21 '18 at 14:28
• @RuudHelderman You may want to see Neim codepage. – JungHwan Min Jun 21 '18 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." – Ruud Helderman Jun 21 '18 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. – JungHwan Min Jun 21 '18 at 22:06

# Haskell, 26 bytes

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


Try it online!

# Mathematica, 17 bytes

Divisors[#][[2]]&


The second smallest divisor.

# APL (Dyalog Extended), 7 2 bytes

⊃⍭


Try it online!

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

# 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%$_)})[0]


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 [0] one thereof. That's left on the pipeline, output is implicit.

# Perl 6, 22 bytes

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


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 '18 at 13:54
• @JoKing D'oh! Of course, can't believe I missed that. Thanks! – Brian J Jun 20 '18 at 13:55

# Haskell, 29 bytes

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][1]


Try it online!

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