Advertisement
Shuva_Dev

Prime Generator - SPOJ Problem (Segmented Sieve)

Jan 25th, 2023
995
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.19 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. #define endl "\n"
  3. #define sp " "
  4. #define ll long long
  5. using namespace std;
  6.  
  7. const int MAX = 1000000;
  8. bool sieve[MAX + 5];
  9.  
  10. void createSieve() {
  11.     for(int i=2; i*i<=MAX; i++) {
  12.         if(sieve[i] == 0) {
  13.             for(int j=i*i; j<=MAX; j+=i) {
  14.                 sieve[j] = 1;
  15.             }
  16.         }
  17.     }
  18. }
  19.  
  20. vector<int> generatePrime(int n) {
  21.     vector<int> primes;
  22.     for(int i=2; i<=n; i++) {
  23.         if(sieve[i]==0) primes.push_back(i);
  24.     }
  25.     return primes;
  26. }
  27.  
  28. int main() {
  29.     createSieve();
  30.     int t, L, R;
  31.     cin >> t;
  32.  
  33.     while(t--) {
  34.         cin >> L >> R;
  35.         int dummy[R-L+1];
  36.         memset(dummy, 0, sizeof(dummy));
  37.         if(L==1) dummy[0] = 1;
  38.         vector<int> primes = generatePrime(sqrt(R));
  39.        
  40.         for(auto pr: primes) {
  41.             int firstMultiple = (L/pr) * pr;
  42.             if(firstMultiple < L) firstMultiple += pr;
  43.  
  44.             for(int i=max(firstMultiple, pr*pr); i<=R; i+=pr) {
  45.                 dummy[i-L] = 1;
  46.             }
  47.         }
  48.         for(int i=L; i<=R; i++) {
  49.             if(dummy[i-L]==0) cout << i << endl;
  50.         }
  51.         cout << endl;
  52.     }
  53.    
  54.    
  55.     return 0;
  56. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement