以幂形式表示的整数 [英] Integer expressed in a power form

问题描述

如果某些 a>可以用幂形式表示数字 N .0 和一些 x>1 ，我们有 N = a ^ x .

现在要检查这一点，我们可以对数取两边，等式变为 log(n)/log(a)= x ，因此通过从(2，sqrt(n))进行迭代如果存在任何将 x 作为整数的数字，而不是赋予该数字 x 幂的数字，则可以表示为 N .

以下是我检查相同的代码

从数学导入日志中的

 ，sqrt，floorn = int(输入())t =地板(sqrt(n))+ 1标志=假对于范围(2，t)中的i:x = log(n)/log(i)如果x == int(x):打印("YESSSSSSSSSSSSSSS！")标志=真休息如果没有标志:打印(Nooooooooooooooooooo！") 

时间复杂度: O ( n )

还有其他替代/更好的方法来解决问题吗?

解决方案

更好的方法是以下算法:

  x<-0我<-2发现<-错误做x<-根(N，i)如果(x是整数)，则发现<-正确万一我<-我+ 1而(x> = 2)和(未找到) 

此算法将比线性算法快得多.我认为这是对数的，但没有时间进行检查.

A number N is said to be expressible in a power form if for some a > 0 and some x > 1, we have N = a^x.

Now to check this we can take log both sides and equation becomes log(n)/log(a)=x so by iterating from (2,sqrt(n))if there exists any number that gives x as a integer than that number to the power x can be expressed as N.

Following is my code that checks for the same

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!")

Time complexity: O(n)

Is there any other alternative/better approach to the problem?

解决方案

A better approach would be the following algorithm:

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)

This algorithm will be much faster than linear. I think it is logarithmic, but do not have the time ti check it.

这篇关于以幂形式表示的整数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！