정수로 표현 된 정수형

Question

숫자 N은 일부 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)

문제에 대한 다른 대안/더 나은 방법이 있습니까?

이

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) 

이 알고리즘은 선형보다 훨씬 빠를 것이다 :

Answer 1

더 좋은 방법은 다음의 알고리즘이 될 것입니다. 나는 그것이 대수적이라고 생각하지만 시간을 확인하지 않아도됩니다.