Project Euler 87

题目

Prime power triples

The smallest number expressible as the sum of a prime square, prime cube, and prime fourth power is \(28\). In fact, there are exactly four numbers below fifty that can be expressed in such a way:

\(\begin{aligned} 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 \end{aligned}\)

How many numbers below fifty million can be expressed as the sum of a prime square, prime cube, and prime fourth power?

解决方案

令\(N=5\times10^7\)。

观察到，这里的和都是质数的\(2\)次方及以上。因此，可以先预处理所有\(\sqrt N\)以内的质数，再将这些质数的\(2,3,4\)次方按序存放在数组\(a_2, a_3, a_4\)中。

直接枚举\(3\)个列表中每个组合，再将\(3\)个数的和存放进集合即可。

代码

from tools import get_prime, int_sqrt

N = 5 * 10 ** 7
M = int_sqrt(N)
pr = get_prime(M)
a2 = [x * x for x in pr]
a3 = [x ** 3 for x in pr if x ** 3 <= N]
a4 = [x ** 4 for x in pr if x ** 4 <= N]
st = set()
for x in a2:
    for y in a3:
        if x + y >= N:
            break
        for z in a4:
            if x + y + z >= N:
                break
            st.add(x + y + z)
ans = len(st)
print(ans)