以下是一个计算a的b次幂的算法:
假定我已有一个质数表,里面包含所有需要用到的质数,并且从小到大排序
定义函数 幂(a,b):
如果 b是0:
返回 1
质数检查范围 = b的平方根向上取整
依次取出质数表中的质数:
如果 质数超出检查范围:
跳出循环
如果 质数整除b:
返回 幂( 幂(a,质数), b/质数 )
返回 a * 幂( a, b-1 )
这个算法的复杂度应该怎样衡量?