fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define ld long double
  3. #define int long long
  4. #define all(v) v.begin(),v.end()
  5. #define allr(v) v.rbegin(),v.rend()
  6. using namespace std;
  7. const int N=1e5+50;
  8. vector<bool>primes(N,0);
  9. vector<int>p;
  10. void sieve(){
  11.     for(int i=1;i<=N;i++)
  12.         primes[i]=true;
  13.     primes[1]=false;
  14.     for(int i=2;i*i<=N;i++){
  15.         if(primes[i]){
  16.             for(int j=i*i;j<N;j+=i){
  17.                 primes[j]=false;
  18.             }
  19.         }
  20.     }
  21.     for(int i=2;i<=N;i++){
  22.         if(primes[i])
  23.             p.push_back(i*i);
  24.     }
  25. }
  26. void solve(){
  27.       int n,k;
  28.      cin>>n>>k;
  29.  
  30.  
  31.       int lans=0,rans=0;
  32.       int l=0,r=p.size()-1;
  33.       while(l<=r){
  34.         int mid=(l+r)/2;
  35.         if(p[mid]>n){
  36.             rans=mid;
  37.             r=mid-1;
  38.  
  39.         }else l=mid+1;
  40.       }
  41.       l=0;r=p.size()-1;
  42.        while(l<=r){
  43.         int mid=(l+r)/2;
  44.         if(p[mid]<=k){
  45.             lans=mid+1;
  46.              l=mid+1;
  47.  
  48.         }else r=mid-1;
  49.       }
  50.       cout<<rans<<" "<<max(0ll,rans-lans)<<"\n";
  51.  
  52.  
  53. }
  54. int32_t main(){
  55.  
  56.     ios_base::sync_with_stdio(false);
  57.     cin.tie(nullptr);
  58.     cout.tie(nullptr);
  59.     sieve();
  60.     int tt=1;
  61.     cin>>tt;
  62.     while(tt--)
  63.         solve();
  64. }
  65.  
Success #stdin #stdout 0.01s 5272KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0 0
https://ideone.com/suyxA1
language:
C++ (gcc 8.3)
created:
22 days 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!