Fastest algorithm for decomposing a perfect power
Python, 207 chars

This takes O(log2 N) bigint ops.  O(log N) different exponents to try, and O(log N) binary search to find each base.

import sys
for N in map(int,sys.stdin.readlines()):
 p,s=2,''
 while 1&lt;&lt;p&lt;=N:
  i,j=2,N
  while j&gt;i+1:
   m=(i+j)/2
   if m**p&gt;N:j=m
   else:i=m
  if i**p==N:s+=' %d^%d'%(i,p)
  p+=1
 if s:print N,'=',s[1:]