Prime Power Switch

Python 2, 56 bytes

while n%p:p+=1

Try it online!

We first find the prime \$p\$ for which \$n=p^q\$ by incrementing \$p\$ until we get a divisor on \$n\$. After that, we find the exponent \$q\$ with a mathematical trick first discovered by Sp3000 and used in Perfect power logarithms on Anarchy Golf.

We note that $$ \frac{n-1}{p-1} = \frac{p^q-1}{p-1} = 1 + p + p^2 \dots+p^{q-2}+p^{q-1}$$ Working modulo \$p-1\$, we have \$p \equiv 1\$, so each of \$q\$ the summands on the right hand side equals 1, and so: $$ \frac{n-1}{p-1} \equiv q \space \bmod (p-1)$$

We'd now like to extract \$q\$. We'd like to get there by applying the modulus operator %(p-1) to the left hand side. But this requires that \$q<p-1\$, which is not guaranteed, or we'll get a different value of q%(p-1).

Fortunately, we can get around this with one more trick. We can replace \$n\$ with \$n^c\$ and \$p\$ with \$p^c\$ for some positive number \$c\$, and still have \$n^c=(p^c)^q\$. Since the exponent \$q\$ relating them is unchanged, we can extract it as above, but make it so that \$q<p^c-1\$. For this, \$c=n\$ more than suffices and is short for golfing, though it makes larger test cases time out.

Bash + Linux utils, 17

factor|dc -e?zr^p
  • factor takes a number as input and factorizes it. The output is the input number, followed by a colon, followed by a spaced-separated list of all the prime factors.
  • This list is piped to dc which evaluates the following expression:
    • ? reads the whole line as input. dc cannot parse the input number followed by the colon, so it ignores it. Then it parses all the space-separated prime factors and pushes them to the stack.
    • z takes the number of items on the stack (number of prime factors) and pushes that to the stack
    • r reverses the top two items on the stack
    • ^ exponentiates, giving the required answer
    • p prints it.

Try it online!

MATL, 8 5 bytes

-3 bytes thanks to @LuisMendo


Try it online!