# How to check if a integer is a power of some integer?

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$.

-
Almost the same question was asked on MathOverflow about a year ago: mathoverflow.net/questions/13843/… –  Jonas Meyer Feb 17 '11 at 23:26
The method you wrote down is very fast. (Except there is no need to reraise it to the power $k$, just check the distance to nearest integer, and see if that is within the error tolerance of the $k^{th}$ rooting algorithmP) What are you doing that needs this to be faster? Whatever your program, it seems unlikely that this is the limiting factor for computation speed. –  Eric Naslund Feb 17 '11 at 23:37