Submission #18225925

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
vector<bool> calc_prime(const int ub)
{
    vector<bool> is_prime(ub + 1, true);
    is_prime.at(0) = is_prime.at(1) = false;
    for (int i = 2; i < ub + 1; ++i) {
        if (!is_prime.at(i))
            continue;
        for (int j = 2 * i; j < ub + 1; j += i)
            is_prime.at(j) = false;
    }
    return is_prime;
}
vector<int> calc_sim2017(const int ub)
{
    auto is_prime = calc_prime(ub);
    vector<int> sim2017(ub + 1, 0);
    for (int N = 3; N < ub + 1; N += 2) { // 2017に似た数は奇数
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <bits/stdc++.h>
using namespace std;

vector<bool> calc_prime(const int ub)
{
    vector<bool> is_prime(ub + 1, true);
    is_prime.at(0) = is_prime.at(1) = false;
    for (int i = 2; i < ub + 1; ++i) {
        if (!is_prime.at(i))
            continue;
        for (int j = 2 * i; j < ub + 1; j += i)
            is_prime.at(j) = false;
    }
    return is_prime;
}

vector<int> calc_sim2017(const int ub)
{
    auto is_prime = calc_prime(ub);
    vector<int> sim2017(ub + 1, 0);
    for (int N = 3; N < ub + 1; N += 2) { // 2017に似た数は奇数
        if (is_prime.at(N) && is_prime.at((N + 1) / 2))
            sim2017.at(N) = 1;
    }
    return sim2017;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    static const int ub = 1e+5;
    auto sim2017 = calc_sim2017(ub);
    vector<int> cumcnt(ub + 2, 0);
    for (int i = 0; i < ub + 1; ++i)
        cumcnt.at(i + 1) = cumcnt.at(i) + sim2017.at(i);
    int Q;
    cin >> Q;
    for (int i = 0; i < Q; ++i) {
        int l, r;
        cin >> l >> r;
        cout << cumcnt.at(r + 1) - cumcnt.at(l) << '\n';
    }
}

Submission Info

Judge Result