fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. vector <int> vec(100000020);
  4. vector <int> prime;
  5. void sieve()
  6. {
  7.     vec[0]=1;
  8.     vec[1]=1;
  9.     for(int i=2;i<=sqrt(100000020);i++){
  10.         if(vec[i]==0){
  11.             prime.push_back(i);
  12.             for(int j=2;j*i<=100000020;j++){
  13.                 vec[j*i]=1;
  14.             }
  15.         }
  16.     }
  17. }
  18. int main()
  19. {
  20.     int t;
  21.     cin >> t;
  22.     sieve();
  23.     for(int i=1;i<=t;i++){
  24.         int l,u,pos2,pos1;
  25.         cin >> l >> u;
  26.         vector <int> ::iterator it1;
  27.         vector <int> ::iterator it2;
  28.         it1=lower_bound(prime.begin(),prime.end(),l);
  29.         it2=lower_bound(prime.begin(),prime.end(),u);
  30.         if(u==0 || u==1){
  31.             pos2=0;
  32.         }
  33.         else if(*it2!=u){
  34.             pos2=it2-prime.begin()-1;
  35.         }
  36.         else{
  37.             pos2=it2-prime.begin()+1;
  38.         }
  39.         if(l==0 || l==1){
  40.             pos1=0;
  41.         }
  42.         else if(*it1!=l){
  43.             pos1=it1-prime.begin()-1;
  44.         }
  45.         else{
  46.             pos1=it1-prime.begin();
  47.         }
  48.         cout << pos2 << "  " << pos1 << endl;
  49.     }
  50. }
Success #stdin #stdout 1.4s 393660KB
comments (?)
stdin
copy 
2
15 19
1 3
stdout
copy 
8  5
2  0
https://ideone.com/HVh5YK
language:
C++14 (gcc 8.3)
created:
2 years 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!