087. 素数幂三元组(Prime power triples)

最小的可以表示为素数的平方、立方与四次方之和的数是28。实际上,五十以内只有四个数可以表示成这样的形式:

$$ 28 = 2^2 + 2^3 + 2^4\\ 33 = 3^2 + 2^3 + 2^4\\ 49 = 5^2 + 2^3 + 2^4\\ 47 = 2^2 + 3^3 + 2^4 $$
求在五千万以内,有多少个数可以被表示成为素数的平方、立方和四次方之和?

分析:这道题似乎并没有太多可以分析的地方,网上大家的普遍的解法都是暴力计算,基本思路是把特定范围内的素数的平方、立方和四次方求出来并计算它们的和,然后这个和是否在五千万的范围以内,最后统计所有符合要求的数,即为题目所求。根据素数的指数不同,其范围也不同,如果指数为2,则素数的平方不能超过五千万,则素数应该小于\(\sqrt{5\cdot10^7}\),约为7072。同理,可以计算出立方和四次方时素数分别应该小于369和85。

我们可以用python中的sympy库计算特定范围内的素数,然后求出这些数的平方、立方和四次方,然后分别把这些数组合起来求和,组合的方式就是我们求笛卡尔积的方式。为了避免出现重复,我们使用python中自带的数据结构——集合来存储这些和。遍历完成后,我们筛选出集合中小于五千万的数的个数,即为题目所求。代码如下:

# time cost = 2.77 s ± 5.66 ms

from itertools import product
from sympy import primerange

def main(N=5*10**7):
    ans = set()
    square_limit = int(N**(1/2))+1
    cube_limit = int(N**(1/3))+1
    fourth_power_limit = int(N**(1/4))+1
    for i,j,k in product(primerange(1,square_limit),primerange(1,cube_limit),primerange(1,fourth_power_limit)):
        p = i**2 + j**3 + k**4
        ans.add(p)
    return len({x for x in ans if x<N})