# 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. – Erik the Outgolfer Jun 20 '18 at 23:55
• Can we output True instead of 1? Alternatively, float instead of ints? – Jo King Jun 21 '18 at 0:33
• @JoKing yes, yes. – Leaky Nun Jun 21 '18 at 0:34
• @EriktheOutgolfer Challenge accepted :D – DLosc Jun 22 '18 at 4:46

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

# Pyth, 2

Count prime factors:

lP

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

# Bash + GNU utilities, 22

• 2 bytes saved thanks to @H.PWiz and @Cowsquack
factor|tr -cd \ |wc -c

Try it online!

• Does factor|sed s/\ //|wc -w work? – H.PWiz Jun 21 '18 at 10:32
• What about factor|tr -cd \ |wc -c? – user41805 Jun 21 '18 at 11:10

# 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
• I found a much better solution! Editing now... – Sophia Lechner Jun 21 '18 at 1:13

# 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 ) # Attache and Wolfram Language (Mathematica) polyglot, 10 bytes PrimeOmega Simply a builtin for computing the number of prime factors N has. ## Explanation Since N = pk, Ω(N) = Ω(pk) = k, the desired result. # 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. # 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! # 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) – Giuseppe Jun 21 '18 at 15:56 # Stax, $\require{cancel}\xcancel 4 3$ bytes |f% Run and debug it Length of prime factorization. • Ahh.. you're breaking the crossed out 4 is still regular 4 ;( meme. ;p (It was getting old anyway though.. So well done I guess) – Kevin Cruijssen Jun 21 '18 at 7:47 • $\text{Yay, MathJax abuse!}$ But remember to put the cross before the actual bytecount otherwiae the leaderboard snippet may not be able to recognize it. – user202729 Jun 22 '18 at 8:53 # 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! # Brachylog, 2 bytes ḋl Try it online! ### Explanation ḋ Prime decomposition l Length # 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! – dylnan Jun 21 '18 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! # 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!

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.

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

• Submissions must be programs or functions by default, and we don't consider this a function. Both rimf, (full program) and {mf,} (function) would be valid. – Dennis Jun 21 '18 at 20:49
• @Dennis Yeah, I think I'm kind of confused on that. I also looked at allowed stardard io before and wondered about what I should actually submit... I actually wanted to ask a question on meta about that. But you confirmed that, so thanks! – Chromium Jun 22 '18 at 3:19

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

ḍl

Try it online!

# JavaScript (ES6), 37 bytes

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

Try it online!

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

# Pari/GP, 8 bytes

bigomega

Try it online!

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

n->numdiv(n)-1

Try it online!

# Racket, 31 bytes

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