Submission #2545638

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
bool is_prime(long long n) {
  if (n < 2 or n > 2 and n % 2 == 0) return false;
  for (long long i = 3; i * i <= n; i += 2) if(n % i == 0) return false;
  return true;
}
signed main() {
  cin.tie(0); ios::sync_with_stdio(false);
  vector<bool> b(1e5 + 10, false);
  for (int i = 3; i < 1e5; i += 2) {
    if (is_prime(i) and is_prime((i + 1) / 2)) b[i] = true;
  }
  vector<int> csum(1e5 + 10, 0);
  for (int i = 3; i < 1e5 + 10; i += 2) {
    csum[i] = csum[i - 2] + b[i];
  }
  int q; cin >> q;
  vector<int> l(q), r(q); for (int i = 0; i < q; i++) cin >> l[i] >> r[i];
  for (int i = 0; i < q; i++) {
    cout << csum[r[i]] - csum[max(l[i] - 2, 0)] << '\n';
  }
  return 0;
}

Submission Info

Judge Result