# Given a prime power, is it possible to efficiently compute the prime

Suppose that I am given as input the number $p^i$ for some prime $p$ and some positive integer $i$. I wish to find $p$ and $i$.

Is there an algorithm to do this that works in time polynomial in the number of digits of $p^i$?

• – user12859 Feb 27 '17 at 8:26

Let $n$ be the number given. Observe that $2 \leq p \leq n$ and $1 \leq i \leq \log_2(n)$. For each possible value of $i$ in the range $\{1, \ldots, \log_2(n)\}$, you can do a binary search for a $p$ in the range $\{2, \ldots, n\}$ such that $p^{i} = n$.
• Note that you might want to iterate over $i$ beginning with $log_2(n)$ instead of $1$. Otherwise, you might find non-primes for $p$ (e.g. $2^{12} = 8^4$). If you start at $log_2(n)$, the first $p$ you find will always be prime. – Tobias Feb 27 '17 at 9:42