一个关于算法复杂度的问题

Question

以下是一个计算a的b次幂的算法：
假定我已有一个质数表，里面包含所有需要用到的质数，并且从小到大排序

 定义函数 幂(a,b):
    如果 b是0：
        返回 1

    质数检查范围 = b的平方根向上取整
    依次取出质数表中的质数：
        如果 质数超出检查范围：
            跳出循环
        如果 质数整除b：
            返回 幂( 幂(a,质数)， b/质数 )

    返回 a * 幂( a, b-1 )

这个算法的复杂度应该怎样衡量？

Answer 1

复杂度是logN