Advertisement
Falak_Ahmed_Shakib

segment seive

May 25th, 2022
604
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long  ll;
  4. typedef pair<ll,ll> pll;
  5. #define fastread() (ios_base:: sync_with_stdio(false),cin.tie(NULL))
  6. #define fi first
  7. #define se second
  8. #define pb push_back
  9. ll const MOD=1000000007;
  10. #define eb emplace_back
  11. const int N=1e5;
  12. ll a[N+1];
  13. vector<ll>v;
  14. void sieve()
  15. {
  16.   v.pb(2);
  17.   for(ll i=3;i<=N;i+=2)
  18.   {
  19.       if(a[i]==0)
  20.       {
  21.           v.pb(i);
  22.           for(ll j=i+i;j<=N;j+=i)
  23.           {
  24.               a[i]=1;
  25.           }
  26.       }
  27.   }
  28.  
  29.  
  30. }
  31. void segment_seive(ll l,ll r)
  32. {
  33.  
  34.      ll len=r-l+10;
  35.      ll m[len+10];
  36.      memset(m,0,sizeof(m));
  37.      if(l==1)m[0]=1;
  38.      for(ll i=0;v[i]*v[i]<=r;i++)
  39.      {
  40.          // cout<<"base "<<v[i]<<endl;
  41.          ll base=v[i]*v[i];
  42.          if(base<l)base=((v[i]+l-1)/v[i])*v[i];
  43.          for(ll j=base;j<=r;j+=v[i])
  44.          {
  45.              m[j-l]=1;
  46.             // cout<<j<<" ";
  47.          }
  48.      }
  49.  
  50.          for(ll i=l;i<=r;i++)
  51.         {
  52.          if(m[i-l]==0)cout<<i<<endl;
  53.         }
  54.  
  55.  
  56. }
  57. int main()
  58. {
  59.     fastread();
  60.     sieve();
  61.  
  62.     ll t;
  63.     cin>>t;
  64.  
  65.     while(t--)
  66.     {
  67.         ll l,r;
  68.         cin>>l>>r;
  69.         segment_seive(l,r);
  70.  
  71.     }
  72.  
  73.  
  74.  
  75.  
  76.  
  77.  
  78. }
  79.  
  80.  
  81.  
  82.  
  83.  
Advertisement
RAW Paste Data Copied
Advertisement