Quote:
Originally Posted by science_man_88
if he didn't want work I'd say use PARI's ispower() with a loop through base values.
|
With ispower() there's no need to loop at all -- ispower(N) does the right thing. ispower(N, b) is only when you want to check for a particular base and no others.
You should look at the code for it some time, it's fascinating. They check for 2nd, 3rd, and 5th powers separately, then move on to general testing for larger bases. Some amount of trial division is also done so you don't have to check quite as high, IIRC.
Incidentally, Bernstein has a nice paper about doing this test efficiently, in almost-linear time. Pretty impressive stuff.