きままにものづくり

日々の気付いたことなんかを書いてます。

POJ2739 : Sum of Consecutive Prime Numbers

問題

 2 \leq N \leq 10000となるNが与えられる。Nとなる連続する素数の部分和の数を答える。

解法

エラトステネスの篩を用いてあらかじめ素数を求める。しゃくとり法を用いてNとなる素数の部分和の数を求める。

計算量

O(MN)
M:入力の数
N:与えられる数

コード