Node:Perfect Power Algorithm, Previous:Perfect Square Algorithm, Up:Root Extraction Algorithms
Detecting perfect powers is required by some factorization algorithms.
Currently mpz_perfect_power_p is implemented using repeated Nth root
extractions, though naturally only prime roots need to be considered.
(See Nth Root Algorithm.)
If a prime divisor p with multiplicity e can be found, then only roots which are divisors of e need to be considered, much reducing the work necessary. To this end divisibility by a set of small primes is checked.