Recover the prime from the prime power

Question

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

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

Testcases:

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

Scoring: This is code-golf. Shortest answer in bytes wins.

Answer 1

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.

Answer 2

05AB1E, 1 byte

f

Try it online!

Answer 3

Java 8, 46 39 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

Answer 4

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

Answer 5

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

Answer 6

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

Answer 7

Whitespace, 80 61 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.

Answer 8

Funky, 30 bytes

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

Try it online!

Answer 9

JavaScript (ES6), 25 bytes

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

Try it online!

Answer 10

Jelly, 3 bytes

ÆfḢ

Try it online!

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

Answer 11

C (gcc), 28 bytes

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

Try it online!

Answer 12

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

Answer 13

Pyth, 2 bytes

hP

Try it here!

Answer 14

Brachylog, 2 bytes

ḋh

Try it online!

Explanation

ḋ       Prime decomposition
 h      Head

Answer 15

J, 4 bytes

0{q:

Select { the first 0 of the prime factors q:

Try it online!

Answer 16

Neim, 1 byte

Try it online!

Answer 17

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.

Answer 18

Haskell, 26 bytes

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

Try it online!

Answer 19

Mathematica, 17 bytes

Divisors[#][[2]]&

The second smallest divisor.

Answer 20

ARBLE, 19 bytes

index(factors(a),1)

Try it online!

Answer 21

Japt -g, 1 byte

k

Try it here

Answer 22

Python 3, 47 45 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!

Answer 23

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.

Answer 24

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.

Answer 25

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.

Answer 26

Haskell, 29 bytes

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

Try it online!

Answer 27

Pari/GP, 17 bytes

n->factor(n)[1,1]

Try it online!

---

Pari/GP, 17 bytes

n->divisors(n)[2]

Try it online!

Answer 28

Ruby, 100 bytes

require"prime"
i=gets.to_i
Prime.each(i){|p|(1..i).each{|n|c=p**n==i
    puts p if c
    exit if c}}

Try it online!

Answer 29

Stax, 3 bytes

|fh

Run and debug it

First element of prime factorization.

Answer 30

Julia 0.6, 25 bytes

n->[2:n;][n.%(2:n).<1][1]

Try it online!

Answer 31

Ruby, 26 bytes

->n,i=1{(1>n%i+=1)?i:redo}

Try it online!

Answer 32

QBasic, 39 bytes

INPUT x
p=2
WHILE x\p<x/p
p=p+1
WEND
?p

Trial division; finds the first factor greater than 1, which is guaranteed to be the prime factor.

The only trick here is the condition x\p<x/p, which uses integer vs. floating point division to test whether "x is not divisible by p." See this tip for details.