fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define ll long long
  3. #define ull unsigned long long
  4.  
  5. using namespace std;
  6.  
  7.  
  8. /*  Implementing Segmented Sieve of Eratosthenes
  9.  
  10. *   Segmented sieve of Eratosthenes used to find primes in range [a, b]
  11. *
  12. *   Steps
  13. *   1- find all the primes up to sqrt(b), call them primes[]
  14. *   2- create a boolean array is_prime[] with length = b-a+1 and fill it with true
  15. *   3- for each p in primes set is_prime[i*p - a] = false starting at i=ceil(a/p)
  16. *   4- for each is_prime[i]=true print i+a
  17. *
  18. */
  19.  
  20. /* ************** Implementation of Sieve of Eratosthenes ************** */
  21. void sieve(ull start, ull stop)
  22. {
  23.     int range;
  24.     range=(int)sqrt(stop);
  25.     bool arr[range+1];
  26.     memset(arr, true, sizeof(arr));
  27.     int i,j;
  28.     int x;
  29.  
  30.     for(i=2;i<=(int)sqrt(range);i++)
  31.     {
  32.         if(arr[i])
  33.         {
  34.             j=2;
  35.             while((x=i*j) <= range)
  36.             {
  37.                 arr[x]=false;
  38.                 j++;
  39.             }
  40.         }
  41.     }
  42.  
  43.     vector<int> primes;
  44.     int cnt=0;
  45.  
  46.     for(i=2;i<=range;i++)
  47.     {
  48.         if(arr[i])
  49.         {
  50.             primes.push_back(i);
  51.             cnt++;
  52.             //cout<<i<<" ";
  53.         }
  54.     }
  55.  
  56.     /* Printing Primes
  57.  
  58.     cout<<"[ ";
  59.     for(i=0;i<cnt;i++)
  60.     {
  61.         cout<<primes[i]<<", ";
  62.     }cout<<"]\n";
  63.     */
  64.  
  65.     //For segmented SIeve
  66.     int siz=stop-start+1;
  67.     bool isprime[siz];
  68.     memset(isprime, true, sizeof(isprime));
  69.     int index;
  70.  
  71.     for(i=0;i<cnt;i++)
  72.     {
  73.         index=(ceil)((float)start/(float)primes[i]);
  74.         index=(int)index;
  75.         isprime[(index*primes[i])-start]=false;
  76.         //cout<<(index*primes[i])-start<<endl;
  77.     }
  78.  
  79.     for(i=0;i<siz;i++)
  80.     {
  81.         //cout<<isprime[i]<<" ";
  82.         if(isprime[i])
  83.             cout<<i+start<<endl;
  84.     }
  85.  
  86. }/* **********************Segmented Sieve of Eratosthenes ************************** */
  87.  
  88.  
  89.  
  90. int main()
  91. {
  92.     int t;
  93.     cin>>t;
  94.     while(t--)
  95.     {
  96.         int start, stop;
  97.         cin>>start>>stop;
  98.         sieve(start, stop);
  99.     }
  100.  
  101.     return 0;
  102. }
  103.  
Success #stdin #stdout 0s 3280KB
comments (?)
stdin
copy 
1
1 10
stdout
copy 
1
4
5
6
7
8
9
10
https://ideone.com/mebiN5
language:
C++ (gcc 8.3)
created:
9 years 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!