ABC084 D - 2017-like Number

問題ページ
D - 2017-like Number

考えたこと

• f(A) = (1からAのうち条件を満たす数) とすれば f(r) - f(l-1) として計算できるのでf(A)を前計算する
• 10^5までの素数をエラトステネスの篩で列挙して、条件を満たす数を1~10^5までで探せばよさそう
• 条件を満たす数が何かわかったので累積和でf(A)を計算する
• 各クエリをO(1)で求める

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define int ll
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
#ifdef int
const ll INF = (1LL<<60);
#else
const int INF = (1LL<<30);
#endif
const double PI = 3.14159265359;
const double EPS = 1e-12;
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

//素数ならtrue
bool prime[1000000];
int dp[100010];

signed main(void)
{
  int q;
  cin >> q;

  memset(prime, true, sizeof(prime));
  prime[0] = prime[1] = false;
  for (int i = 2; i * i <= 1000000; i++) {
    if (prime[i]) {
      for (int j = 2 * i; j <= 1000000; j += i) {
        prime[j] = false;
      }
    }
  }

  FOR(i, 1, 100010) {
    if(i%2 && prime[i] && prime[(i+1)/2]) {
      dp[i] = 1;
    }
  }

  FOR(i, 1, 100010) dp[i] += dp[i-1];

  REP(i, q) {
    int l, r;
    cin >> l >> r;
    cout << dp[r] - dp[l-1] << endl;
  }

  return 0;
}