以幂形式表示的整数

一个号码N据说可以用幂形式表达，如果对于某些a > 0还有一些x > 1， 我们有N = a^x.

现在为了检查这一点，我们可以取两边的对数，方程变为log(n)/log(a)=x所以通过迭代(2,sqrt(n))如果存在任何给出的数字x作为该数的幂的整数x可以表示为N.

以下是我检查相同内容的代码

from math import log,sqrt,floor
n=int(input())
t=floor(sqrt(n))+1
flag=False


for i in range(2,t):
    x=log(n)/log(i)
    if x==int(x):
        print("YESSSSSSSSSSSSS!")
        flag=True
        break

if not flag:
    print("Nooooooooooooooooooo!")

时间复杂度：O(n)

是否有其他替代/更好的方法来解决该问题？

更好的方法是以下算法：

x <- 0
i <- 2
found <- false
do
    x <- root(N, i)
    if (x is integer) then
       found <- true
    end if
    i <- i + 1
while (x >= 2) and (not found)

该算法将比线性算法快得多。我认为它是对数的，但没有时间检查它。