Submission #3010387

---

Source Code Expand

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <queue>
#include<string>
#include<cstring>
#include<complex>
#include<cmath>
using namespace std;
#define rep(i, n)   for(int i = 0; i < (int)(n); i++)
#define rrp(i, n)   for(int i = ((int)(n)); i >=0; i--)
#define mpp(i,j,k)  make_pair((int)(i),make_pair((int)(j),(int)(k)))
typedef pair<int,pair<int,int > > ppp;
typedef pair<int,int> pp;
typedef vector<int> vi;
typedef vector<vi>  vvi;
bool d[100001];
int  q[100001];
bool prime(int x){
if(x==1)return false;
if(x==2)return true;
if(x%2==0) return false;
for(int i=3;i<=sqrt(x);i+=2)if(x%i==0) return false;

return true;
}
int main(){
 rep(i,100001){d[i]=prime(i);}
 rrp(i,100001){if(i%2==1)d[i]&=d[(i+1)/2];}
d[2]=false;
 rep(i,100001){q[i]=0;if(d[i])q[i]=1;if(i>0)q[i]+=q[i-1];}
int Q;
int l[100000],r[100000];
cin>>Q;
rep(i,Q)cin>>l[i]>>r[i];
rep(i,Q)cout<<q[r[i]]-q[l[i]-1]<<endl;
  return 0;}

Submission Info

Judge Result