Perfect Power detection in linear time

Question

I'm trying to write a C program which, given a positive integer n (> 1) detect whether exists numbers x and r so that n = x^r

This is what I did so far:

while (c>=d) {
    double y = pow(sum, 1.0/d);
    if (floor(y) == y) {
        out = y;
        break;
    }

    d++;
}

In the program above, "c" is the maxium value for the exponent (r) and "d" will start by being equal to 2. Y is the value to be checked and the variable "out" is set to output that value later on. Basically, what the script does, is to check if the square roots of y exists: if not, he tries with the square cube and so on... When he finds it, he store the value of y in "out" so that: y = out^d

My question is, is there any more efficient way to find these values? I found some documentation online, but that's far more complicated than my high-school algebra. How can I implement this in a more efficient way?

Thanks!

Answer 1

In one of your comments, you state you want this to be compatible with gigantic numbers. In that case, you may want to bring in the GMP library, which supports operations on arbitrarily large numbers, one of those operations being checking if it is a perfect power.

It is open source, so you can check out the source code and see how they do it, if you don't want to bring in the whole library.