Submission #3414877

---

Source Code Expand

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=int(a);i<int(b);++i)
#define SIZE 100005
#define INF 1000000005LL
#define MOD 1000000007

using namespace std;
typedef long long int ll;
typedef pair <int,int> P;

int N;
int A[SIZE];
ll K;
bool ip[SIZE];
int ps[SIZE];

int main()
{
	int Q;
	cin >> Q;
	int p=0;
	rep(i,0,SIZE)ip[i] = true;
	ip[0] = ip[1] = false;
	rep(i,2,SIZE){
		if(ip[i]) for(int j=2*i;j<=SIZE;j+=i) ip[j] = false;
	}
	int t = 0;
	rep(i,0,SIZE){
		if(ip[i] && ip[(i+1)/2])t++;
		ps[i] = t;
	}
	int l,r;
	rep(i,0,Q){
		cin >> l >> r;
		cout << ps[r]-ps[l-1] << endl;
	}

	return 0;
}

Submission Info

Judge Result