How to check if a number is a perfect power in polynomial time
Given a number n, if at all it can be written as $a^b$ (b > 1), then $b &lt; \log(n) + 1$. And for every fixed $b$, checking if there exists an $a$ with $a^b = n$ can be done using binary search. The total running time is therefore $O(\log^2 n)$ I guess.