Integer root extracting

[Torbjorn Granlund]

Hans Aberg <haberg-1 at telia.com> writes:

  GMP has a function mpz_perfect_power_p() that for given integer a
  tells if a = x^y is solvable in integers x, y with y > 1. But I need
  to find the largest y for which this is true (and also finding x). One
  way to do this is to prime factor a and take the gcd of the exponents,
  but is there a faster method?
  
Completely factoring a is of course not always possible.

A more tractable algorithm is the following:

for y = floor(log(a)/log(2)) to 2 by -1
  If a^(1/y) is an integer, return y

The starting value is the largest power y for which a^(1/y) >= 2.

Testing if a^(1/y) can be done efficienty by computing mod some small
numbers; thus most non-solutions can be quickly rejected.

-- 
Torbjörn