AOJ 0053 (Sum of Prime Numbers : 素数の和)
【問題】
https://onlinejudge.u-aizu.ac.jp/problems/0053
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0053
【概要】
【解説】
各データセットに対してO(1)で返せるようにするために、あらかじめ累積和の配列(i番目にi番目までの素数の合計を格納した配列)を用意しておく。
素数の判定は、整数を順にエラトステネスの篩を利用して判定すればよい。判定の結果、素数であれば、その素数自身と配列の前の要素の合計を配列に格納していくことで、累積和の配列を作ることができる。
【コード】