# Recover the power from the prime power

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 pn where p is a prime and n is a natural number.

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

Testcases:

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


Scoring: This is . Shortest answer in bytes wins.

• Note: This challenge might be trivial in some golfing languages, but it's not so trivial for some mainstream languages, as well as the language of June 2018, QBasic. Jun 20, 2018 at 23:55
• Can we output True instead of 1? Alternatively, float instead of ints?
– Jo King
Jun 21, 2018 at 0:33
• @JoKing yes, yes. Jun 21, 2018 at 0:34
• @EriktheOutgolfer Challenge accepted :D Jun 22, 2018 at 4:46

# 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!

# 05AB1E, 2 bytes

Òg


Try it online!

# 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.

# R 22 bytes

Power n is the number of multiples of p in p^n when p is prime:

sum(!(b<-scan())%%2:b)


Try it online!

## Nibbles 5 bytes

,|,$~^%@  This is 9 nibbles each of which is encoded in a half byte in the binary form. I think this is the shortest solution that doesn't use built in factoring. Translation: , length | filter ,$  0..input
~    not \x->
^   pow (so that 0 which would have been 0 from the mod isn't)
%  mod
@ input
implicit $(x) implicit$ (x)


It works by just counting the number of numbers the input divides evenly

You could run it passing in a list of numbers to process in stdin or as a command line arg. Nibbles isn't on TIO.run yet...

# Pyth, 2

Count prime factors:

lP


# 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 )

# 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
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}

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}
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}
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}

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}
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}

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}
NSSSSN     Create Label_BREAK_2           [9,3,2,1]       {0:9}
TNST      Print as integer               [9,3]           {0:9}           2
error


Program stops with an error: No exit found.

# Brachylog, 2 bytes

ḋl


Try it online!

### Explanation

ḋ        Prime decomposition
l       Length


D,f,@,bUbU$^= L,dVfbUG$XGRzGGXzÞ{f}bUbU0$:  Try it online! I don't even know where to begin explaining this mess. ## Explained D,f,@,bUbU$^=
D,f,@,        ; a helper function f that given a list [number, [x, y]]
bUbU$^ ; returns whether x ^ y = ; equals number L,dVfbUG$XGRzGGXzÞ{f}bUbU0$: L, ; a lambda that dV ; places its input into the register fbU ; and gets the prime factor of the input. This is guaranteed to be a single item because the input is a prime raised to a power. G$X                    ; push a list of input copies of that power
GRz                 ; and zip that with the range [1...input]
GGX              ; also, push input copies of the input
z             ; and zip that with our big list. I'm calling it a big list because it is what it is.
Þ{f}         ; filter that list based on the results of the helper function f
bUbU0$: ; get the power out of the many nested lists returned.  • 34 bytes. You can replace f with g, per this tip to save 2 bytes, use the full flatten command BF instead of two unpacks and use some stack manipulation to replace 0$: Jan 5 at 13:18

# QBasic, 51 41 bytes

INPUT n
FOR i=2TO n
f=f-(n/i=n\i)
NEXT
?f


-10 bytes by copying the approach from Darren Smith's Nibbles answer: For a prime power input, the desired output equals the number of integers between 1 (exclusive) and the input (inclusive) that evenly divide the input.

INPUT number
FOR testFactor = 2 TO number
' number is divisible by testFactor if their float division equals
' their int division
isDivisible = (number / testFactor = number \ testFactor)
' Truthy is -1 in QBasic, so we subtract rather than add to the tally
numFactors = numFactors - isDivisible
NEXT testFactor
PRINT numFactors


# HBL, 7 bytes

(or possibly 6.5 depending on how this meta question shakes out)

+(*'?(*%.(02.


Try it!

### Explanation

+(*'?(*%.(
(0    Inclusive range
2    from 2
.   to the argument
(*        Map over each value x in that list:
%.       Argument mod x
(*            Map over each value in that list:
'?           Logical negation
The result is a list containing 1 for each number that divides
the argument, 0 otherwise
+              Take its sum


# Risky, 3 bytes

!\?___


Try it online!

A basically built-in solution for now, working on a non-trivial version (might not be possible given Risky's heavy investment in specific operators, and generally awful control flow).

!      Count
\     Prime factors
?    Input


# 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

# J, 4 bytes

#@q:


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

Try it online!

# R, 37 bytes

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


Try it online!

• sum(x|1) is nearly always shorter than length(x) Jun 21, 2018 at 15:56

# 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


# Jelly, 3 2 bytes

Æḍ


Try it online!

# Vyxall, 1 byte

ǐ


Try it Online!

-1 byte thx to @lyxal

Length of the prime factors, the flags are cheaty+awesome

• Try it Online! for 1 byte May 22, 2021 at 11:44

# MS Excel, 33 bytes

An anonymous worksheet function that takes input from cell A1 and outputs to the calling cell

-SUM(-(MOD(A1,SEQUENCE(A1))<1))-1


# 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.

• You can save three bytes by making it a full program: Try it online! Jun 21, 2018 at 0:23

# Japt, 3 bytes

k l


Try it online!

## Explanation:

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


# Actually, 2 bytes

ol


Try it online!

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


Try it online!

Counts factors. Compare:

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


Try it online!

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


Try it online!

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


Try it online!

# 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.