Finding integer power roots

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 .

Solution

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: