2017-like Number [AtCoder Beginner Contest 084 D]

https://abc084.contest.atcoder.jp/tasks/abc084_d

前提知識

• 素数判定（エラトステネスの篩）
• 累積和

解法

https://abc084.contest.atcoder.jp/submissions/1932091

[1,100000]の素数表を予め作っておこう。
これはエラトステネスの篩を使うことでO(NlogN)で全て構築できる
　
次に、次の配列を作る。
「A[i] := 数iが2017に似た数ならば1、そうでないなら0」
これは素数表がすでに完成されていれば直ぐに構築できる。
　
最後に、クエリに高速に答える手段を考える。
これは累積和を使おう。
「B[i] := [0,i]の数の中で2017に似た数の個数」
配列Aができていれば、配列Bを作るのは難しくない。

int Q;
int A[101010], B[101010];
//---------------------------------------------------------------------------------------------------
void _main() {
    auto ps = makeBitPrimes(101010);
    rep(i, 1, 101010) if (ps[i] and ps[(i + 1) / 2]) A[i] = 1;
    rep(i, 1, 101010) B[i] = B[i - 1] + A[i];
 
    cin >> Q;
    rep(q, 0, Q) {
        int L, R;
        cin >> L >> R;
 
        int ans = B[R] - B[L - 1];
        printf("%d\n", ans);
    }
}