整数表达为指数形式

Question

一个数N可以用幂形式表示，如果对于一些a > 0和一些x > 1，我们有N = a^x。你知道吗

现在要检查这个，我们可以把log两边都取，方程变成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）

有没有其他更好的方法来解决这个问题？你知道吗

Answer 1

更好的方法是以下算法：

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)

这种算法将比线性算法快得多。我认为它是对数的，但我没有时间检查它。你知道吗