_no0B

Untitled

Nov 28th, 2021
660
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. #define ll long long
  3. #define N ((int)6e4 + 5)
  4. #define MOD ((int)1e9 + 7)
  5. #define MAX ((int)1e9 + 7)
  6. #define MAXL ((ll)1e18 + 7)
  7. #define MAXP ((int)1e3 + 7)
  8. #define thr 1e-8
  9. #define pi acos(-1)  /// pi = acos ( -1 )
  10. #define fastio ios_base::sync_with_stdio(false),cin.tie(NULL)
  11. #define endl "\n"
  12.  
  13. using namespace std;
  14.  
  15. int isPrime[N/32 + 2];
  16.  
  17. bool IsPrime(int num) /// returns 1 for prime
  18. {
  19.     if(num == 2) return 1;
  20.     if((num & 1) == 0)  return 0;
  21.     int idx  = num >> 5 , bit = num & 31;
  22.     if( ( isPrime[idx] & (1<<bit) ) != 0 ) return 0;
  23.     else return 1;
  24. }
  25.  
  26. vector < int > BitwiseSieve(int n)
  27. {
  28.     for(int i = 3; i * i <= n ; i += 2){
  29.         if(IsPrime(i)){
  30.             for(int j = i * i ; j <= n ; j += i<<1){
  31.                 int idx = j >> 5 , bit = j & 31;
  32.                 isPrime[idx] = isPrime[idx] | (1<<bit);
  33.             }
  34.         }
  35.     }
  36.     vector < int > prime;
  37.     prime.push_back(2);
  38.     for(int i = 3 ; i <= n ; i += 2){
  39.         if(IsPrime(i)) prime.push_back(i);
  40.     }
  41.     return prime;
  42. }
  43.  
  44.  
  45.  
  46.  
  47.  
  48.  
  49.  
  50.  
  51.  
  52.  
  53.  
  54.  
  55.  
RAW Paste Data