C++ Program to Implement Segmented Sieve

This C++ Program demonstrates the implementation of Segmented Sieve.

Here is source code of the C++ Program to demonstrate the implementation of Segmented Sieve. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. /* 
  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. }

$ g++ sieve_segemented.cpp
$ a.out
 
Enter Lower Bound: 7
Enter Upper Bound: 600
Number of primes between 7 and 600:  106
 
------------------
(program exited with code: 1)
Press return to continue

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

advertisement
advertisement
If you wish to look at all C++ Programming examples, go to C++ Programs.

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.