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$.
Como Jonas Meyer dice, el post de mathoverflow contiene toda la información.
El problema puede resolverse en tiempo casi lineal por este papel.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
