Given a integer $n$, we want to know if $n=m^k$ for some $m$ and $k>1$. What is the fastest method? (Suppose the factors of $n$ are not given).
The best method I can think of is to try to calculate $n^\frac{1}{k}$ to a certain precision, for $k$ from $2$ to $\log_2 n$. Determine if $n^\frac{1}{k}$ is a integer by test if $\lfloor n^\frac{1}{k} \rfloor ^k = n$.