Previous: Perfect Square Algorithm, Up: Root Extraction Algorithms [Index]

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.