We have a natural number $n>1$. We want to determine whether there exist
natural numbers $a, k>1$ such that $n = a^k$. 


Please suggest a polynomial-time algorithm.



How to quickly determine whether a given natural number is a power of another natural number?
This can be done in "essentially linear time." Check out Daniel Bernstein's website: <http://cr.yp.to/arith.html>


Especially note his papers labeled [powers] and [powers2].


