将一个数分解为两个幂的和

Question

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';

谢谢 ！

Answer 1

您可以通过查找所有小于 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，在大多数情况下您可以提前停止。