Submission #2543183

---

Source Code Expand

#include <iostream>

using namespace std;
int sosu_sum[100005];
int sosu[100005];

int main(){
    sosu_sum[1] =1;
    sosu[2] =1;
    for(int i = 3; i < 100001; i +=2){
        bool issosu = true;
        for(int j =3; j < i ;j +=2){
            if(i %j ==0){
                issosu =false;
                break;
            }
        }
        if(issosu){
            sosu[i] =1;
            if(sosu[(i +1)/2]==1){
                sosu_sum[i] = sosu_sum[i-2] + 1;
                continue;
            }
        }
        sosu_sum[i] = sosu_sum[i-2];
    }
    int Q, l, r;
    cin >>Q;
    
    for(int i =0 ; i < Q; i++){
        cin >> r >> l;
        cout << sosu_sum[l] - sosu_sum[r-2]<< endl;
    }

    return 0;
}
    

Submission Info

Judge Result