Recover the power from the prime power

Question

It seems that many people would like to have this, so it's now a sequel to this challenge!

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 power n.

Testcases:

input output
9     2
16    4
343   3
2687  1
59049 10

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

Answer 1

05AB1E, 2 bytes

Òg

Try it online!

Answer 2

Python 3, 49 bytes

f=lambda n,x=2:n%x and f(n,x+1)or n/x<2or-~f(n/x)

Try it online!

Outputs True instead of 1 (as allowed by OP). Recursive function that repeatedly finds the lowest factor and then calls the function again with the next lowest power until it reaches 1. This is an extension of my answer to the previous question.

Answer 3

Pyth, 2

Count prime factors:

lP

Online test.

Answer 4

Bash + GNU utilities, 22

• 2 bytes saved thanks to @H.PWiz and @Cowsquack

factor|tr -cd \ |wc -c

Try it online!

Answer 5

Python 2, 37 bytes

f=lambda n,i=2:i/n or(n%i<1)+f(n,i+1)

Try it online!

Counts factors. Apparently I wrote the same golf in 2015.

Narrowly beats out the non-recursive

Python 2, 38 bytes

lambda n:sum(n%i<1for i in range(1,n))

Try it online!

Answer 6

dc, 50 41 bytes

1si[dli1+dsi%0<X]dsXx[dli/dli<Y]sYdli<Yzp

Try it online!

Takes input from the top of the stack (in TIO, put the input in the header to load it onto the stack before execution). Outputs to stdout.

Explanation

Registers used:

i: the current trial divisor, while X is running. Later, the divisor we've found.

X: the macro dli1+dsi%0<X, which has the effect "increment i, then check the modulus with the value on the stack (which will be the original input). If it's not zero, repeat".

Y: the macro dli/dli<Y, which has the effect "Add to the stack a copy of the current top of the stack, divided by i. Repeat until i is reached."

Full program:

1si                 Initialize i
[dli1+dsi%0<X]dsXx  Define and run X
[dli/dli<Y]sY       Define Y
dli<Y               Run Y, but only if needed (if the input wasn't just i)
z                   The stack is i^n, i^(n-1), ... ,i, so print the stack depth

Answer 7

face, 86 bytes

(%d@)\$*,c'$,io>Av"[""mN*c?*m1*mp*m%*s1"$pN1p:~+p1p%%Np?%~:=/NNp+?1?-%N1?%=p%'$i?w1'%>

Hooray, longer than Java!

Try it online!

I am particularly fond of the trick of using the return value of sscanf. Normally the return value would be discarded, but here it will always be 1, because we're always reading a single number as input. We can take advantage of this by assigning its return value to the variable 1, saving the 2 bytes that would otherwise be required to assign 1 to 1 explicitly.

(%d@)

\$*,c'$,io>  ( setup - assign $ to "%d", * to a number, o to stdout )
Av"[""mN*    ( set " to input and allocate space for N for int conversion )
c?*          ( calloc ?, starting it at zero - this will be the output )
m1*          ( allocate variable "1", which gets the value 1 eventually )
mp*m%*       ( p is the prime, % will be used to store N mod p )

s1"$pN       ( scan " into N with $ as format; also assigns 1 to 1 )

1p:~         ( begin loop, starting p at 1 )
  +p1p       ( increment p )
  %%Np       ( set % to N mod p )
?%~          ( repeat if the result is nonzero, so that we reach the factor )

:=           ( another loop to repeatedly divide N by p )
  /NNp       ( divide N by p in-place )
  +?1?       ( increment the counter )
  -%N1       ( reuse % as a temp variable to store N-1 )
?%=          ( repeat while N-1 is not 0 -- i.e. break when N = 1 )

p%'$i?       ( sprintf ? into ', reusing the input format string )
w1'%>        ( write to stdout )

Answer 8

Attache and Wolfram Language (Mathematica) polyglot, 10 bytes

PrimeOmega

Try Attache online! Try Mathematica online!

Simply a builtin for computing the number of prime factors N has.

Explanation

Since N = p^k, Ω(N) = Ω(p^k) = k, the desired result.

Answer 9

Jelly, 3 2 bytes

Æḍ

Try it online!

Answer 10

Java 8, 59 bytes

A lambda from int to int.

x->{int f=1,c=0;while(x%++f>0);for(;x>1;c++)x/=f;return c;}

Try It Online

Answer 11

J, 4 bytes

#@q:

q: gives the list of prime factors, # gives the length of the list.

Try it online!

Answer 12

R, 37 bytes

length(numbers::primeFactors(scan()))

Try it online!

Answer 13

Stax, \$\require{cancel}\xcancel 4 3\$ bytes

|f%

Run and debug it

Length of prime factorization.

Answer 14

MATL, 3 bytes

Yfz

Try it online!

Explanation:

     % Implicit input: 59049
Yf   % Factorize input [3, 3, 3, 3, 3, 3, 3, 3, 3, 3]
  z  % Number of non-zero elements: 10
     % Implicit output

Answer 15

Whitespace, 141 bytes

[S S S N
_Push_0][S N
S _Duplicate_0][T   N
T   T   _Read_STDIN_as_number][T    T   T   _Retrieve][S S S T  N
_Push_1][N
S S N
_Create_Label_LOOP_1][S S S T   N
_Push_1][T  S S S _Add][S N
S _Duplicate][S T   S S T   S N
_Copy_2nd_input][S N
T   _Swap_top_two][T    S T T   _Modulo][N
T   S S N
_If_0_Jump_to_Label_BREAK_1][N
S N
N
_Jump_to_Label_LOOP_1][N
S S S N
_Create_Label_BREAK_1][S S S N
_Push_0][S T    S S T   S N
_Copy_2nd_input][N
S S T   N
_Create_Label_LOOP_2][S N
S _Duplicate_input][S S S T N
_Push_1][T  S S T   _Subtract][N
T   S S S N
_If_0_Jump_to_Label_BREAK_2][S N
T   _Swap_top_two][S S S T  N
_Push_1][T  S S S _Add][S N
T   _Swap_top_two][S T  S S T   S N
Copy_2nd_factor][T  S T S _Integer_divide][N
S N
T   N
_Jump_to_Label_LOOP_2][N
S S S S N
_Create_Label_BREAK_2][S N
N
_Discard_top][T N
S T _Print_as_number]

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 input
Integer f = 1
Start LOOP_1:
  f = f + 1
  if(n modulo-f == 0)
    Call function BREAK_1
  Go to next iteration of LOOP_1

function BREAK_1:
  Integer r = 0
  Start LOOP_2:
    if(n == 1)
      Call function BREAK_2
    r = r + 1
    n = n integer-divided by f
    Go to next iteration of LOOP_2

function BREAK_2:
  Print r as number to STDOUT
  Program stops with an error: Exit not defined

Example run: input = 9

Command    Explanation                    Stack           Heap    STDIN   STDOUT   STDERR

SSSN       Push 0                         [0]
SNS        Duplicate top (0)              [0,0]
TNTT       Read STDIN as number           [0]             {0:9}   9
TTT        Retrieve                       [9]             {0:9}
SSSTN      Push 1                         [9,1]           {0:9}
NSSN       Create Label_LOOP_1            [9,1]           {0:9}
 SSSTN     Push 1                         [9,1,1]         {0:9}
 TSSS      Add top two (1+1)              [9,2]           {0:9}
 SNS       Duplicate top (2)              [9,2,2]         {0:9}
 STSSTSN   Copy 2nd from top              [9,2,2,9]       {0:9}
 SNT       Swap top two                   [9,2,9,2]       {0:9}
 TSTT      Modulo top two (9%2)           [9,2,1]         {0:9}
 NTSSN     If 0: Jump to Label_BREAK_1    [9,2]           {0:9}
 NSNN      Jump to Label_LOOP_1           [9,2]           {0:9}

 SSSTN     Push 1                         [9,2,1]         {0:9}
 TSSS      Add top two (2+1)              [9,3]           {0:9}
 SNS       Duplicate top (3)              [9,3,3]         {0:9}
 STSSTSN   Copy 2nd                       [9,3,3,9]       {0:9}
 SNT       Swap top two                   [9,3,9,3]       {0:9}
 TSTT      Modulo top two (9%3)           [9,3,0]         {0:9}
 NTSSN     If 0: Jump to Label_BREAK_1    [9,3]           {0:9}
NSSSN      Create Label_BREAK_1           [9,3]           {0:9}
SSSN       Push 0                         [9,3,0]         {0:9}
STSSTSN    Copy 2nd from top              [9,3,0,9]       {0:9}
NSSTN      Create Label_LOOP_2            [9,3,0,9]       {0:9}
 SNS       Duplicate top (9)              [9,3,0,9,9]     {0:9}
 SSSTN     Push 1                         [9,3,0,9,9,1]   {0:9}
 TSST      Subtract top two (9-1)         [9,3,0,9,8]     {0:9}
 NTSSSN    If 0: Jump to Label_BREAK_2    [9,3,0,9]       {0:9}
 SNT       Swap top two                   [9,3,9,0]       {0:9}
 SSSTN     Push 1                         [9,3,9,0,1]     {0:9}
 TSSS      Add top two (0+1)              [9,3,9,1]       {0:9}
 SNT       Swap top two                   [9,3,1,9]       {0:9}
 STSSTSN   Copy 2nd from top              [9,3,1,9,3]     {0:9}
 TSTS      Integer-divide top two (9/3)   [9,3,1,3]       {0:9}
 NSNTN     Jump to Label_LOOP_2           [9,3,1,3]       {0:9}

 SNS       Duplicate top (3)              [9,3,1,3,3]     {0:9}
 SSSTN     Push 1                         [9,3,1,3,3,1]   {0:9}
 TSST      Subtract top two (3-1)         [9,3,1,3,2]     {0:9}
 NTSSSN    If 0: Jump to Label_BREAK_2    [9,3,1,3]       {0:9}
 SNT       Swap top two                   [9,3,3,1]       {0:9}
 SSSTN     Push 1                         [9,3,3,1,1]     {0:9}
 TSSS      Add top two (1+1)              [9,3,3,2]       {0:9}
 SNT       Swap top two                   [9,3,2,3]       {0:9}
 STSSTSN   Copy 2nd from top              [9,3,2,3,3]     {0:9}
 TSTS      Integer-divide top two (3/3)   [9,3,2,1]       {0:9}
 NSNTN     Jump to Label_LOOP_2           [9,3,2,1]       {0:9}

 SNS       Duplicate top (1)              [9,3,2,1,1]     {0:9}
 SSSTN     Push 1                         [9,3,2,1,1,1]   {0:9}
 TSST      Subtract top two (1-1)         [9,3,2,1,0]     {0:9}
 NTSSSN    If 0: Jump to Label_BREAK_2    [9,3,2,1]       {0:9}
NSSSSN     Create Label_BREAK_2           [9,3,2,1]       {0:9}
 SNN       Discard top                    [9,3,2]         {0:9}
 TNST      Print as integer               [9,3]           {0:9}           2
                                                                                    error

Program stops with an error: No exit found.

Answer 16

Brachylog, 2 bytes

ḋl

Try it online!

Explanation

ḋ        Prime decomposition
 l       Length

Answer 17

Python 2, 62 bytes

def f(n,p=2,i=0):
	while n%p:p+=1
	while n>p**i:i+=1
	return i

Try it online!

Nothing fancy here.

Answer 18

Japt, 3 bytes

k l

Try it online!

Explanation:

k l
k     Get the prime factors of the input
  l   Return the length

Answer 19

Actually, 2 bytes

ol

Try it online!

Answer 20

Haskell, 27 bytes

f n=sum$(0^).mod n<$>[2..n]

Try it online!

Counts factors. Compare:

Haskell, 28 bytes

f n=sum[1|0<-mod n<$>[2..n]]

Try it online!

Haskell, 28 bytes

f n=sum[0^mod n i|i<-[2..n]]

Try it online!

Haskell, 30 bytes

f n=sum[1|i<-[2..n],mod n i<1]

Try it online!

Answer 21

Octave, 18 bytes

@(x)nnz(factor(x))

Try it online!

Does what it says on the tin: Number of non-zero elements in the prime factorization of the input.

Answer 22

Cjam, 5 bytes

rimf,

Try it Online!

Explanation:

ri      take the input and convert it to an int
  mf    factors the input
    ,   take the length of the list

Builtins are great!

Answer 23

QBasic, 51 bytes

INPUT x
p=2
WHILE x/p>x\p
p=p+1
WEND
?LOG(x)/LOG(p)

Uses the same algorithm as the "Recover the prime" solution to find the base, then uses rules of logarithms to get the exponent: \$log(p^n) = n \cdot log(p)\$.

Answer 24

Gaia, 2 bytes

ḍl

Try it online!

Answer 25

JavaScript (ES6), 37 bytes

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

Try it online!

Answer 26

Perl 6, 36 bytes

{round .log/log (2..*).first: $_%%*}

Looks for the first factor (2..*).first: $_%%*, then from there calculates the approximate value (logs won't get it exact) and rounds it.

Try it online!

Answer 27

Pari/GP, 8 bytes

bigomega

Try it online!

bigomega(x): number of prime divisors of x, counted with multiplicity.

---

Pari/GP, 14 bytes

n->numdiv(n)-1

Try it online!

Answer 28

Racket, 31 bytes

(car(cdr(perfect-power(read))))

Try it online!

Answer 29

Perl 6, 18 bytes

{+grep($_%%*,^$_)}

Try it online!

Anonymous code block that gets a list of factors and coerces it to a number.

Answer 30

JavaScript (Node.js), 29 bytes

f=(n,k=n)=>--k&&!(n%k)+f(n,k)

Try it online! Note: Stack overflows for larger inputs.

Answer 31

F#, 91 bytes

let rec d n c v=if v=n then c else d(n/v)(c+1)v
let p n=d n 1(Seq.find(fun x->n%x=0){2..n})

Try it online!

p gets the prime factor. d recursively divides the target value until it's equal to the prime factor and returns the count from that.