Memory and time efficient :)
Problem Statement:
Your are given two integers a and b. You have to find all the primes within range a and b. Here, 1 ≤ a ≤ b ≤ 231-1 and b - a ≤ 105.
Note: You have to handle 1, 2 and even numbers for appropriate case of your own.
Solution:
#include <string.h>
#define MAX 46656
#define LMT 216
#define LEN 4830
#define RNG 100032
unsigned base[MAX/64], segment[RNG/64], primes[LEN];
#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)))
/* 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;
}
This is a sample program which demonstrates segmented sieve. Very fast and memory efficient version. 'base' is the array which holds the flags for all the primes upto √(2
31-1), i.e. the square-root of the max limit, and all the primes are stored in the 'primes' array. Later, these primes are used to determine whether a number is a composite or not within a certain range in the segmented sieve. To avoid overflow and sign bit problems, unsigned type is used.
A little explanation:
First of what what these macros mean?
#define MAX 46656
#define LMT 216
#define LEN 4830
#define RNG 100032
MAX is the sqrt of maximum possible input, in case of here, the maximum is integer range sqrt of which is almost MAX used here. So, MAX is not maximum allowed input, it is just sqrt of maximum input which is pretty big as 2147483647 i.e. 32 bit signed integer maximum.
LMT is sqrt of MAX. We all know, we run sieve upto sqrt MAX
LEN is the maximum possible different primes that can be stored using this algorithm with specific range defined as
RNG, on which the segmented sieve will run and collect the primes out of it.
Now the next two vital macros:
#define chkC(x,n) (x[n>>6]&(1<<((n>>1)&31)))
#define setC(x,n) (x[n>>6]|=(1<<((n>>1)&31)))
And why we divide by 64:
Ok, yes, it is clearly bit shifting. But you must know what we do in bitwise sieve first in order to get this. Instead of using a whole array position to store just one flag, we can use its each 32 bits to store one flag, which saves memory by a factor 1/32. So its very logical to capture memory upto MAX/32, but why MAX/64 and RNG/64 here?
Because, we really have no point of handling the even number as 2 is the only even prime and we can handle it manually, without any stress. So, if we do not consider the even numbers at all, the total numbers are again reduced by a factor 1/2, isn't it? So what we get total is MAX/32/2 = MAX/64, same for RNG.
Now, the two macros chkC and setC is pretty straight forward. chkC checks if a specific bitflag is 1 or 0, and setC sets a specific bitflag 1 to mark it as a composite. They work similarly, so I will explain only the chkC part.
In bitwise sieve, where is a specific value n located? Obviously (n/32)
th index, and on that index, (n%32)
th bit from LSB (right hand side). But we just said before, we are interested with only odd numbers, so we map n with n/2 as follows:
Actual numbers
1 2 3 4 5 6 7 8 9 ........... n ;[n is odd]
| | | | | | | | | ........... |
0 x 1 x 2 x 3 x 4 ........... (n/2)
Position on which they are represented in the bitstrings.
So, n is actually n/2, which implies the previous statement: n's (actually n/2 's) position is in index [n/2/32] = [n/64] = [n>>6] and on the bit position (n/2)%32 = (n>>1)&31 ;[ We know, modding with a power of 2 is same as ANDing with (same power of 2)-1 ]. The rest is, how we check / set this specific bit. I have another post explaining these operations:
Bitwise operations in C: Part 3, and obviously you can google it :)
