【Project Euler】Problem 50: 連続した素数の和で表される素数

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

問題 50. 連続した素数の和

原文 Problem 50: Consecutive prime sum

問題の要約：連続した素数の和で表される$10^6$以下の素数の中で、連続した素数が最も長いものを求めよ

連続した素数の和を求めるのにちょうど良いnumpyのcumsumという関数があったので使って見ました。

まずどんな関数か試してみます。20以下の素数のリストで見てみるとcumsumの結果の大きい方から素数を探せば2から始まる一番長い連続した素数の和が見つかります（この場合は41）。

import numpy as np
l = [2,3,5,7,11,13,17,19]
print(np.cumsum(l))
#[ 2  5 10 17 28 41 58 77]

これをもとにしたプログラムです。

import numpy as np
from sympy import primerange, isprime
plist = [p for p in primerange(1,10000)]
maxCon = 0
for st in range(0,100):                # Shifting the starting position
  priSum = np.cumsum(plist[st:])       # cumulative sum of the primes
  for n in range(len(priSum)-1, maxCon,-1): # Seach max prime in priSum
    if priSum[n] < 10**6 and isprime(priSum[n]): 
      maxCon, startP, lastP, maxConPrime = n, plist[st], plist[st+n], priSum[n]
      break

print(f"Answer : {maxConPrime}, {maxCon+1} consecutive primes ({startP}-{lastP})")

（開発環境：Google Colab）