【Project Euler】Problem 60: 連結素数の集合

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

問題 60. 連結素数の集合

原文 Problem 60: Prime pair sets

**問題の要約：5個の素数から2組を連結した数もすべての素数になるような5個の素数の和の最小値を求めよ。

まず2個の素数の連結したものが素数になることをチェックする関数isCatPrimeを作ります。これは後から何度も呼ばれるのでメモ化で高速化するために@lru_cacneを指定します。

from sympy import isprime, primerange
from functools import lru_cache
@lru_cache(maxsize=None)
def isCatPrime(p1,p2):
  return isprime(int(str(p1)+str(p2))) and isprime(int(str(p2)+str(p1)))

次に既に見つかった連結素数のリストに対して新たな素数p1がリストのすべての素数と連結素数になるがチェックする関数isAllCatPrimesです。

# return True, only when p1 is CatPrime with all of p in plist
def isAllCatPrimes(p1, plist): 
  for p2 in plist:
    if not isCatPrime(p1,p2): return False
  return True

これで準備は整ったので再帰関数findMoreで、リストの長さが5になるまで検索します。

# return 5 prime set when found, otherwise return []
def findMore(foundPr, remPr):   # found primes list, remaining primes to be searched
  if len(foundPr) == 5:
    return foundPr
  for pp in range(len(remPr)):
    p = remPr[pp]
    if isAllCatPrimes(p, foundPr): # check p is cat prime pair with all of foundPr
      Pr5 = findMore(foundPr + [p], remPr[pp+1:]) 
      if len(Pr5)>0: return Pr5
  return []

N = 10**4
Primes = list(primerange(2,N))   # Prime list
for pp in range(len(Primes)):
  Pr5 = findMore([Primes[pp]],Primes[pp+1:])
  if len(Pr5)>0: 
    print(Pr5, sum(Pr5))

（開発環境：Google Colab）