Project Euler [Problem 50]

みんな大好き素数列シリーズその２

連続する素数の和がまた素数になってるやつ

問題

Consecutive prime sum

The prime 41, can be written as the sum of six consecutive primes:

41 = 2 + 3 + 5 + 7 + 11 + 13

This is the longest sum of consecutive primes that adds to a prime below one-hundred.

The longest sum of consecutive primes below one-thousand that adds to a prime, contains 21 terms, and is equal to 953.

Which prime, below one-million, can be written as the sum of the most consecutive primes?

私訳

連続する素数の和

41 は 6 つの連続する素数の和として書くことができる : 41 = 2 + 3 + 5 + 7 + 11 + 13 これは100 未満で最長の「連続する素数の和で書ける素数」である 1000 未満だと 21 項の 953 が最長となる。

100 万未満で最長となる素数はいくつだろうか？

解答方針

一般に で、素数列でも非常に大雑把には和は2乗より速いペースで増加すると思われる。 なので、10⁶ までの素数は 10³ くらいまでの和を考えてればよさそう。 余裕をもって 10⁴ くらいにしますかね。 で、素数判定は平方根取れればいいはずだし、表としてはそれくらいにして、和が素数なら ok と。