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; }