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.
/*
* C++ Program to Implement Segmented Sieve
*/
#include <iostream>
#include <cstring>
#define MAX 46656
#define LMT 216
#define LEN 4830
#define RNG 100032
#define sq(x) ((x)*(x))
#define mset(x,v) memset(x, v , sizeof(x))
#define chkC(x,n) (x[n >> 6] & (1 << ((n >> 1) & 31)))
#define setC(x,n) (x[n >> 6] |= (1 << ((n >> 1) & 31)))
using namespace std;
unsigned base[MAX/64], segment[RNG/64], primes[LEN];
/*
* Generates all the necessary prime numbers and marks them in base[]
*/
void sieve()
{
unsigned i, j, k;
for (i = 3; i < LMT; i += 2)
{
if (!chkC(base, i))
{
for (j = i * i, k = i << 1; j < MAX; j += k)
setC(base, j);
}
}
for (i = 3, j = 0; i < MAX; i += 2)
{
if (!chkC(base, i))
primes[j++] = i;
}
}
/*
* Returns the prime-count within range [a,b] and marks them in segment[]
*/
int segmented_sieve(int a, int b)
{
unsigned i, j, k, cnt = (a <= 2 && 2 <=b )? 1 : 0;
if (b < 2)
return 0;
if (a < 3)
a = 3;
if (a % 2 == 0)
a++;
mset (segment, 0);
for (i = 0; sq(primes[i]) <= b; i++)
{
j = primes[i] * ((a + primes[i] - 1) / primes[i]);
if (j % 2 == 0) j += primes[i];
for (k = primes[i] << 1; j <= b; j += k)
{
if (j != primes[i])
setC(segment, (j - a));
}
}
for (i = 0; i <= b - a; i += 2)
{
if (!chkC(segment, i))
cnt++;
}
return cnt;
}
/*
* Main
*/
int main()
{
sieve();
int a, b;
cout<<"Enter Lower Bound: ";
cin>>a;
cout<<"Enter Upper Bound: ";
cin>>b;
cout<<"Number of primes between "<<a<<" and "<<b<<": ";
cout<<segmented_sieve(a, b)<<endl;
return 0;
}
$ 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.
Related Posts:
- Practice Computer Science MCQs
- Apply for Computer Science Internship
- Check C++ Books
- Check Computer Science Books
- Check Programming Books