Checking whether an integer is a square or higher power

Is there an algorithm to check whether an integer $n$ is a square? What about higher powers, e.g., testing whether $n$ is a $k$th power?

I understand that the Jacobi symbol $\left(\frac{b}{n}\right)$ can be computed in $O(\log n)$ without needing to know the prime factorization of $n$ but then this seems to be useful only for squares (not higher powers), and even then, it can still be inconclusive.

Maybe there is some way of refining the use of the Jacobi symbol for my question?

The standard algorithm for determining whether an integer $n$ is a perfect power goes like this. We check whether it is a perfect $k$th power for $k \in \{2,\ldots,\log n\}$; as an optimization, it suffices to consider only prime $k$. Given $k$, we compute $\sqrt[k]{n}$ using binary search or using some fixed-point iteration such as Newton's method. Either way, we find a candidate for $\sqrt[k]{n}$, and can check whether $(\sqrt[k]{n})^k = n$ or not. For more details on computing $\sqrt[k]{n}$, consult for example this paper (mentioned in Ricky Demer's deleted answer), Step 1.

StackExchange Computer Science Q#26379, answer score: 4