「この範囲内(l～r)の個数を求めよ」というクエリが10^5個とかある時、累積和で前準備 abc084_d

累積和 エラトステネスのふるい

Quiz

https://atcoder.jp/contests/abc084/tasks/abc084_d

Submit

https://atcoder.jp/contests/abc084/submissions/3879182

要素

  • エラトステネスのふるい（今回はなくてもよい）
  • 累積和
  • left～rightでの個数＝＞f(v) : 0～vまでの個数を求めておき、f(right) - f(left-1)

追記：2020/10/19

// 素数判定
bool isPrime(ll n){
    if (n < 2) return false;
    else if (n == 2) return true;
    else if (n % 2 == 0) return false;

    double sqrtNum = sqrt(n);
    for (ll i=3; i<=sqrtNum; i+=2){
        if (n%i == 0){
            return false;
        }
    }
    return true;
}

ll A[100010];

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    FOR(i,2,100001){
      if(isPrime(i) && isPrime((i+1)/2)) A[i]=1;
    }
    rep(i,100005){
      A[i+1] += A[i];
    }
    ll Q;cin>>Q;
    while(Q--){
      ll l,r;cin>>l>>r;
      ll ans = A[r] - A[l-1];
      p(ans);
    }
    
    return 0;
}