Submission #3413329

---

Source Code Expand

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
typedef long long  ll;
#define rep(i,s,n)for(ll i=s;i<n;i++)
#define repe(i,s,n)for(ll i=s;i<=n;i++)

bool p[100001];
bool q[100001];
int main()
{
	ll maxV = 100000;
	rep(i, 0, maxV)p[i] = true;
	p[0] = false;
	p[1] = false;

	for (int i = 2; i*i <= maxV; i++) {
		if (!p[i])continue;
		for (int j = 2; i*j <= maxV; j++) {
			if (i*j <= maxV) {
				p[i*j] = false;
			}
		}
	}

	rep(i, 0, maxV) {
		q[i] = p[i];
	}

	rep(i, 0, maxV) {
		if (p[i] && p[(i + 1) / 2]) {
			q[i] = true;
		}
		else {
			q[i] = false;
		}
	}
	ll s[100001] = {};
	rep(i, 1, maxV) {
		s[i] += s[i - 1] + (q[i] ? 1 : 0);
	}

	ll Q; cin >> Q;
	rep(i, 0, Q) {
		ll l, r; cin >> l >> r;
		cout << s[r] - s[l - 1] << endl;
	}

	return 0;
}

Submission Info

Judge Result