fork(17) download
copy 
  1. /* Run it on offline compilers like Codeblocks or Orwell/Blooodshed Dev C++
  2.  * C++ Program to Implement Segmented Sieve
  3.  */
  4. #include <iostream>
  5. #include <cstring>
  6. #define MAX 46656
  7. #define LMT 216
  8. #define LEN 4830
  9. #define RNG 100032
  10. #define sq(x) ((x)*(x))
  11. #define mset(x,v) memset(x, v , sizeof(x))
  12. #define chkC(x,n) (x[n >> 6] & (1 << ((n >> 1) & 31)))
  13. #define setC(x,n) (x[n >> 6] |= (1 << ((n >> 1) & 31)))
  14. using namespace std;
  15. unsigned base[MAX/64], segment[RNG/64], primes[LEN];
  16.  
  17. /* 
  18.  * Generates all the necessary prime numbers and marks them in base[]
  19.  */
  20. void sieve()
  21. {
  22.     unsigned i, j, k;
  23.     for (i = 3; i < LMT; i += 2)
  24.     {
  25.         if (!chkC(base, i))
  26.         {    
  27.             for (j = i * i, k = i << 1; j < MAX; j += k)
  28.                 setC(base, j);
  29.         }
  30.     }
  31.     for (i = 3, j = 0; i < MAX; i += 2)
  32.     {
  33.         if (!chkC(base, i))
  34.             primes[j++] = i;
  35.     }
  36. }
  37.  
  38. /*
  39.  * Returns the prime-count within range [a,b] and marks them in segment[] 
  40.  */
  41. int segmented_sieve(int a, int b)
  42. {
  43.     unsigned i, j, k, cnt = (a <= 2 && 2 <=b )? 1 : 0;
  44.     if (b < 2) 
  45.         return 0;
  46.     if (a < 3) 
  47.         a = 3;
  48.     if (a % 2 == 0) 
  49.         a++;
  50.     mset (segment, 0);
  51.     for (i = 0; sq(primes[i]) <= b; i++)
  52.     {
  53.         j = primes[i] * ((a + primes[i] - 1) / primes[i]);
  54.         if (j % 2 == 0) j += primes[i];
  55.         for (k = primes[i] << 1; j <= b; j += k)
  56.         {
  57.             if (j != primes[i])
  58.                 setC(segment, (j - a));
  59.         }
  60.     }
  61.     for (i = 0; i <= b - a; i += 2)
  62.     {
  63.         if (!chkC(segment, i))
  64.             cnt++;
  65.     }
  66.     return cnt;
  67. }
  68. /* 
  69.  * Main
  70.  */
  71. int main()
  72. {
  73.     sieve();
  74.     int a, b;
  75.     cout<<"Enter Lower Bound: ";
  76.     cin>>a;
  77.     cout<<"Enter Upper Bound: ";
  78.     cin>>b;
  79.     cout<<"Number of primes between "<<a<<" and "<<b<<":  ";
  80.     cout<<segmented_sieve(a, b)<<endl;
  81.     return 0;
  82. }
Not running #stdin #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Mm37uq
language:
Text (text 6.10)
created:
9 years ago
visibility:
secret

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!