Checking whether an integer is a square or higher power
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.