Finding integer power roots

Question

What is the best (most efficient) algorithm for finding all integer power roots of a number?

That is, given a number n, I want to find b (base) and e (exponent) such that

n = b^e

I want to obtain all the possible value pairs of b and e

Ps: n b and e are to be positive integers .

Answer 1

First find the prime factorization of n: n = p1e1 p2e2 p3e3 ...

Then find the greatest common divisor g of e1, e2, e3, ... by using the Euclidean algorithm.

Now for any factor e of g, you can use:

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

And you have n = be.

Answer 2

I think brute force approach should work: try all es from 2 (1 is a trivial solution) and up, taking r = n ^ 1/e, a double. If r is less than 2, stop. Otherwise, compute ceil(r)^e and floor(r)^e, and compare them to n (you need ceil and floor to compensate for errors in floating point representations). Assuming your integers fit in 64 bits, you would not need to try more than 64 values of e.

Here is an example in 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;
}

When invoked with 65536, it produces this output:

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