Previous: Perfect Square Algorithm, Up: Root Extraction Algorithms [Index]
完全べき乗を見つけるには,いくつかの因数分解アルゴリズムを組み合わせて使う必要があります。
現状の実装では mpz_perfect_power_p
関数は,素数べき乗根についての考慮は必要になりますが, Nべき乗根を繰り返すようになっています(See Nth Root Algorithm)。
素数因子pがe個見つかったとすると,eの因数となるべき乗根だけ考慮すればよく,計算の節約ができます。 そのためには,小さい素数で割り切れるかどうかをチェックすることになります。