【AtCoder版！蟻本】AtCoder-ABC084 D - 2017-like Number【エラトステネスの篩】
AtCoder版！蟻本のエラトステネスの篩の例題としてあげられているABC084 D - 2017-like Number をPythonで解いていきます。
リンク
ABC084 D - 2017-like Number
問題文
「N も (N+1)÷2 も素数」を満たす奇数 N を 2017に似た数 とします。
Q 個のクエリが与えられます。
クエリ i(1≦i≦Q) では奇数 l i ,r i が与えられるので、l i ≦ x ≦ r i かつ 2017に似た数 となる奇数 x の個数を求めてください。
制約
・1≦Q≦10^5
・1 ≦ l i ≦ r i ≦ 10^5
・l i ,r i は奇数
・入力は全て整数
解答例
解説
「N も (N+1)÷2 も素数」を満たす奇数 N を 2017に似た数 として、与えられたQ個のクエリについてLi <= x <= Riかつ2017に似た数となるxの個数を答える問題です。
まずエラトステネスの篩でriの最大値10^5までの素数をprime配列に列挙します。
エラトステネスの篩はこちらのページで記載しましたので参照してください。
ebisuke33.hatenablog.com
次に2017に似た数字の数を調べるためlike2017配列を作成し、primeに格納された数が2017に似た数か判定しました。
tmpに(N+1)÷2 を代入し、このtmpがprime配列にあれば2017に似た数なのでprime配列の該当する要素に1を足します。
2017に似た数字を調べ終えると、変数sumに累積和をとりlike2017配列をsumで更新しました。
最後に各クエリに対して、riまでの累積和num_rから li - 1までの累積和num_lを引けば求める解答です。
AtCoder版！蟻本（初級編）の記事リンクページはこちら
ebisuke33.hatenablog.com
リンク
