View Single Post
Old 2011-04-13, 23:05   #4
CRGreathouse's Avatar
Aug 2006

3×1,987 Posts

Originally Posted by science_man_88 View Post
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.

Last fiddled with by CRGreathouse on 2011-04-13 at 23:06
CRGreathouse is offline   Reply With Quote