Project Euler 87

python

問題は、Problem 87 - Project Euler。
50 * 10^6以下の数の中で、素数の二乗+三乗+四乗でかけるものの数を求めよというものです。

解答している人が前後の問題と比べて二倍程多いだけあって単純な総当たりでも数秒程で答えがでてしまいます。

from number_theory import *

p1 = primes(int(pow(50 * 10**6, 0.5)))
p2 = primes(int(pow(50 * 10**6, 1.0/3.0)))
p3 = primes(int(pow(50 * 10**6, 1.0/4.0)))

candidates = []

for x in p1:
    for y in p2:
        for z in p3:
            candidates += [x**2 + y**3 + z**4]

print len([x for x in set(candidates) if x < 50 * 1000000])