x 是我的输入。
我需要找到 i,j>=0 和 n,m>1,例如 x = i**m+j**n
目前我一直在这样做,但速度太慢了!!我该如何改进它?
from math import sqrt
import numpy as np
def check(x):
for i in range(1,int(np.ceil(sqrt(x)))):
for j in range(1,int(np.ceil(sqrt(x)))):
for m in range(2,x/2+1):
for n in range(2,x/2+1):
if((pow(i,m) +pow(j,n))==x):
print 'Yes';
return ;
print 'No';
谢谢!
最佳答案
您可以通过找到小于 x 的所有幂 (i**m) 来逆转该过程。然后你只需检查这些幂中的任何一对是否加起来等于 x。
def check(x):
all_powers = set([1]) #add 1 as a special case
#find all powers smaller than x
for base in range(2,int(math.ceil(sqrt(x)))):
exponent = 2;
while pow(base, exponent) < x:
all_powers.add(pow(base, exponent))
exponent+=1
#check if a pair of elements in all_powers adds up to x
for power in all_powers:
if (x - power) in all_powers:
print 'Yes'
return
print 'No'
上面的代码很简单但可以优化,例如,通过在 while 循环中集成检查一对加起来是否为 x,您可以在大多数情况下提前停止。
关于python - 将一个数拆分为两个幂的和,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/48730424/