farhin_khaled

Segmented Sieve

May 17th, 2022 (edited)
183
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define       ll       long long int
  5. #define       ull      unsigned long long int
  6. #define       ld       long double
  7.  
  8. #define       pf       printf
  9. #define       sf       scanf
  10.  
  11. #define       pb       push_back
  12. #define       pob      pop_back
  13. #define       ph       push
  14. #define       pp       pop
  15. #define       mp       make_pair
  16. #define       ins      insert
  17. #define       f        first
  18. #define       sc       second
  19.  
  20. #define       eps      (double)(1e-7)
  21. #define       M        (ll)(1e6)
  22. #define       LM       (ll)(1e18)
  23. #define       mod      (ll)(1e6+7)
  24. #define       MAX      32000
  25.  
  26. vector <int> primes;
  27. bool marked[M];
  28.  
  29. void sieve(){
  30.   primes.pb(2);
  31.   for(int i=3;i<=MAX;i+=2){
  32.     if(!marked[i]){
  33.       primes.pb(i);
  34.       for(int j=i*i;j<=MAX;j+=i){
  35.         marked[j] = true;
  36.       }
  37.     }
  38.   }
  39. }
  40.  
  41. void segSieve(int u,int l){
  42.   bool isPrime[(l-u)+1];
  43.   int cnt = 0;
  44.   for(int i=0;i<(l-u)+1;i++){
  45.     isPrime[i] = true;
  46.   }
  47.   for(int i=0;primes[i]*primes[i]<=l;i++){
  48.     int curPrime = primes[i];
  49.     ll fmul = (u/curPrime)*curPrime;
  50.     if(fmul<u){
  51.       fmul += curPrime;
  52.     }
  53.     for(int j=fmul;j<=l;j+=curPrime){
  54.       isPrime[j-u] = false;
  55.     }
  56.     if(fmul==curPrime){
  57.       isPrime[fmul-u] = true;
  58.     }
  59.   }
  60.   for(int i=0;i<(l-u)+1;i++){
  61.     if(isPrime[i]){
  62.       cout << i+u << endl;
  63.     }
  64.   }
  65. }
  66.  
  67. int main()
  68. {
  69.   sieve();
  70.   segSieve(2,17);
  71.  
  72.   return 0;
  73. }
RAW Paste Data Copied