【Project Euler】Problem 87: 素数のべき乗の和

• 本記事はProjectEulerの「100番以下の問題の説明は記載可能」という規定に基づいて回答のヒントが書かれていますので、自分である程度考えてみてから読まれることをお勧めします。

問題 87. 素数のべき乗の和

原文 Problem 87: Prime power triples

問題の要約：素数の2乗・3乗・4乗の和で表せる数が$5*10^7$未満でいくつあるか求めよ

50未満では以下の4個だけです。

単純に全探索します。同じような処理が繰り返されるので再帰関数で実装しました。重複を除くためにセットを使っています。

import sympy
def countPPT(ppt, pw, PPTmax):
  if pw == 1:
    if ppt < PPTmax: 
      pptSet.add(ppt)
    return 
  for p in Primes:
    ppt1 = ppt+p**pw 
    if ppt1 >= PPTmax: break
    countPPT(ppt1,pw-1, PPTmax)
  return 

PPTmax, pptSet = 5*10**7, set({})
Primes = list(sympy.primerange(2,int(PPTmax**(1/2))))

countPPT(0, 4, PPTmax)
print(f"Answer: {len(pptSet)}")

（開発環境：Google Colab）