Encontrar raíces de poder enteras

Question

¿Cuál es el mejor algoritmo (más eficiente) para encontrar todas las raíces de poder enteros de un número?

Es decir, dado un númeron, quiero encontrarb (base) y e (exponente) de tal manera que

n = b ^e

Quiero obtener todos los pares de valores posibles de b y e

Sal: nb y e han de ser números enteros positivos .

Answer 1

Creo que el enfoque de fuerza bruta debería funcionar: pruebe todos e s de 2 (1 es una solución trivial) y más, tomando r = n^1/e, double. Si r es menor que 2, deténgase. De lo contrario, calcule ceil(r)^e y floor(r)^e, y compárelos con n (necesita ceil y floor para compensar los errores en las representaciones de coma flotante). Suponiendo que sus enteros encajen en 64 bits, no necesitaría probar más de 64 valores de e.

Aquí se muestra un ejemplo en C++:

#include <iostream> 
#include <string> 
#include <sstream> 
#include <math.h> 
typedef long long i64; 
using namespace std; 
int main(int argc, const char* argv[]) { 
    if (argc == 0) return 0; 
    stringstream ss(argv[1]); 
    i64 n; 
    ss >> n; 
    cout << n << ", " << 1 << endl; 
    for (int e = 2 ; ; e++) { 
     double r = pow(n, 1.0/e); 
     if (r < 1.9) break; 
     i64 c = ceil(r); 
     i64 f = floor(r); 
     i64 p1 = 1, p2 = 1; 
     for (int i = 0 ; i != e ; i++, p1 *= c, p2 *= f); 
     if (p1 == n) { 
      cout << c << ", " << e << endl; 
     } else if (p2 == n) { 
      cout << f << ", " << e << endl; 
     } 
    } 
    return 0; 
} 

Cuando se invoca con 65536, que produce este resultado:

65536, 1 
256, 2 
16, 4 
4, 8 
2, 16 

Answer 2

Depende de las dimensiones de la tarea si mi enfoque se ajustará a sus necesidades.

Antes que nada hay una solución obvia: e = 1, ¿no? A partir de ahí si quiere encontrar todas las soluciones: todos los algoritmos que se me ocurren requieren para encontrar algún factor primo de n. Si esto es solo una tarea independiente, no se puede hacer nada mejor que la fuerza bruta en los números primos (si no estoy equivocado). Después de encontrar el primer factor primo p y su exponente correspondiente (es decir, el número más alto k tal que p^k/n) necesita comprobar e solo los divisores de k. Para cada uno de estos exponentes l (de nuevo itera todos los divisores de k) puede usar la búsqueda binaria para ver si la raíz l de n es un número entero (equivalente a encontrar una nueva solución).

Answer 3

En primer lugar encontrar la factorización prima de n: n = p1e1 p2e2 p3e3 ...

luego encontrar el máximo común divisor de ge1, e2, e3, ... Al usar el Euclidean algorithm.

Ahora para cualquier factor de e de g, puede utilizar:

b = p1e1/e p2e2/e p3e3/e ...

Y tiene n = be.

Answer 4

mezclar los enfoques de interjay y dasblinkenlight. Primero busca todos los factores primos pequeños (si los hay) y sus exponentes en la factorización prima de n. El valor apropiado de 'pequeño' depende de n, por medio de tamaño n, p <= 100 puede ser suficiente, por grann, p <= 10000 o p <= 10^6 puede ser más apropiado. Si encuentra algún pequeño factor primo, sabe que e debe dividir el mayor divisor común de todos los exponentes que encontró. Muy a menudo, ese gcd será 1. De todos modos, el rango de posibles exponentes se reducirá, si n no tiene factores primos pequeños, usted sabe que e <= log(n)/log(small_limit), que es una buena reducción de log(n)/log(2), si ha encontrado un par de pequeños factores, el gcd de sus exponentes es g, y el cofactor restante de n es m, solo necesita verificar los divisores g que no excedan log(m)/log(small_limit).