Sieve algorithms for perfect power testing (Q2366224)

Many tests for primality of \(n\) first require the elimination of the case where \(n\) is a perfect \(k\)-th power. This is negligible compared with the main primality routines, so it is usually ignored. There is a rich variety of methods including Newton's root extraction with starting value found by counting digits, modular tests for \(k\) power and search for small prime divisors (for elimination). On a more sophisticated level there is the (logarithmic number of) parallel processors, and the ERH to bound the trial moduli for power tests. (This requires a small table for efficiency.) The worst case is \(O(\log^ 3 n)\), the average is \(O(\log^ 2 n)\), and \(O(\log n)\) is the median.