Submission #1924275

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define L 100001
long q;
vector < long > prim(L,0);
void init()
{
    long i,j;
    vector < long > tmp(L,1);
    for (i=2;i<=sqrt(L);i++)
        if (tmp[i])
            for (j=2*i;j<L;j+=i)
                tmp[j]=0;
    tmp[0]=tmp[1]=0;
    for (i=1;i<L;i+=2)
        if (tmp[i]&&tmp[(i+1)/2]) prim[i]=1;
}
void solve()
{
    while(q--)
    {
        long i,l,r,ans=0;
        cin>>l>>r;
        for (i=l;i<=r;i++)
            if (prim[i]) ans++;
        cout<<ans<<endl;
    }
}
int main()
{
    init();
    while(cin>>q)
        solve();
}

Submission Info

Judge Result