整数が電力形式で表現されている

Question

数字がの場合、a > 0と一部の場合はx > 1の場合は、N = a^xとなります。我々は両側と式ログ取ることができ、これを確認するために今

はNのように表すことができるxパワーにその数以上の整数としてxを与える任意の数が存在する場合(2,sqrt(n))から反復によってそうlog(n)/log(a)=xなります。続き

は同じ

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) 

このアルゴリズムは、線形よりもはるかに高速になります。私はそれが対数だと思うが、時間をチェックしていない。