www.delorie.com/gnu/docs/gmp/gmp_109.html

search

	Buy GNU books!

GNU MP 4.1.2

16.5.4 Perfect Power

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 section 16.5.2 Nth Root.)

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.