¿Cómo verificar si un entero es una potencia de algún número entero?

Question

Dado un número entero $n$, queremos saber si $n=m^k$ $m$ y $k>1$. ¿Qué es el método más rápido? (Suponga que no se dan los factores de la $n$).

El mejor método que se me ocurre es intentar calcular $n^\frac{1}{k}$ a una cierta precisión, $k$ $2$ $\log_2 n$. Determinar si $n^\frac{1}{k}$ es un número entero por prueba si $\lfloor n^\frac{1}{k} \rfloor ^k = n$.

Answer 1

Como Jonas Meyer dice, el post de mathoverflow contiene toda la información.

El problema puede resolverse en tiempo casi lineal por este papel.