fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define ll long long
  5. #define nl "\n"
  6. #define vi vector<int>
  7. #define all(v) v.begin(), v.end()
  8. #define SORT(v) sort(all(v))
  9. #define SORTX(v) sort(v.begin(), v.end(), greater<int>())
  10. #define read(a) for (auto &i : a) cin >> i
  11. #define Printv(a) for (auto &i : a) cout << i << " "
  12. #define pii pair<int, int>
  13. #define M_ShahaT ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  14.  
  15.  
  16. void FIO(){
  17. #ifndef ONLINE_JUDGE
  18.     freopen("Input.txt","r",stdin);
  19.     freopen("Output.txt","w",stdout);
  20. #endif
  21. }
  22. int dx[] = {1, 0, -1, 0, -1, -1, 1, 1};
  23. int dy[] = {0, -1, 0, 1, -1, 1, -1, 1};
  24. char di[] = {'D', 'L', 'U', 'R'};
  25. double const PI=acos(-1);
  26. const ll INF = 1e18;
  27. const ll mod=1e9+7;
  28. const int N = 1e6 + 5;
  29. int f_1_to_n(int n){
  30.     return n*(n+1)/2;
  31. }
  32. bool valid(int x,int y,int row ,int col){
  33.     return x<row&&x>=0&&y<col&&y>=0;
  34. }
  35.  
  36. vector<bool>vis(N);
  37. vector<int>prime;
  38. void sieve(){
  39.     for(ll i=2;i<N;i++){
  40.         if(!vis[i]){
  41.             prime.push_back(i);
  42.             for(ll j = i*i;j<=N;j+=i){
  43.                 vis[j]=true;
  44.             }
  45.         }
  46.     }
  47. }
  48. /*
  49.  
  50.  
  51.  */
  52.  
  53. vector<int>pre;
  54.  
  55. int binary(int n){
  56.  
  57.     return lower_bound(prime.begin(), prime.end(), n) - prime.begin();
  58.  
  59. }
  60.  
  61. void solve_case() {
  62.     int a,b;cin>>a>>b;
  63.     int inda= binary(a);
  64.     int indb= binary(b);
  65.    //if(prime[inda]>a)inda--;
  66.    if(prime[indb]>b && indb>0 )indb--;
  67.  // cout<<inda<<" "<<indb<<nl;
  68.   //cout<<prime[inda]<<" "<<prime[indb]<<nl;
  69.   if(inda>0)inda--;
  70.  cout << pre[indb] - pre[inda];
  71. }
  72.  
  73.  
  74. int main(){
  75.     M_ShahaT
  76.     FIO();
  77. //2 3 5 7 11
  78.     int t=1;
  79.     sieve();
  80.     pre.assign(prime.size()+1,0);
  81.  
  82.     for(int i=2;i<prime.size();i++){
  83.         if((abs(prime[i-1]-prime[i-2])==2 && abs(prime[i]-prime[i-1])==4 ||
  84.             (abs(prime[i-1]-prime[i-2])==4 && abs(prime[i]-prime[i-1])==2) )){
  85.             pre[i]=pre[i-1]+1;
  86.         }else {
  87.             pre[i]=pre[i-1];
  88.         }
  89.     }
  90.     cin >> t;
  91.     for(int i=1;i<=t;i++){
  92.  
  93.         solve_case();
  94.         cout<<nl;
  95.     }
  96.     return 0;
  97. }
Success #stdin #stdout 0.02s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-1202
https://ideone.com/Uwb7lr
language:
C++ (gcc 8.3)
created:
23 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!