ABC084: D - 2017-like Number

問題

D - 2017-like Number

解説

以下の素数情報が分かればよいためエラトステネスの篩を事前に行っておく。 ある数に対して2017と似た数であるかどうかは、事前計算によってで求まる。 区間の中での数を数える問題だが、各々の数で独立に条件の判定しているだけなので、累積和を取っておくことででの計算量で事前計算すればで数え上げることが出来る。

int main() {
    vector<bool> is_prime(100001, true);
    is_prime[0] = is_prime[1] = 0;
    for (int i = 2; i <= 100000; i++) {
        if (!is_prime[i]) continue;
        for (int j = 2 * i; j <= 100000; j += i) {
            is_prime[j] = 0;
        }
    }
    vector<int> sum(100001);
    for (int i = 0; i <= 100000; i++) {
        sum[i] = is_prime[i] && is_prime[(i + 1) / 2];
    }
    for (int i = 0; i < 100000; i++) {
        sum[i + 1] += sum[i];
    }
    int Q; cin >> Q;
    while (Q--) {
        int l, r; cin >> l >> r;
        cout << sum[r] - sum[l - 1] << "\n";
    }
}