I came across the following method of generating primes using an optimized sieve.
I know the naive sieve of eratosthenes and its implementation but am not able to understand the
following code :
how does it work ?(the use of bitwise operators)
#define N 51000000
unsigned int prime[N / 64];
#define gP(n) (prime[n>>6]&(1<<((n>>1)&31)))
#define rP(n) (prime[n>>6]&=~(1<<((n>>1)&31)))
void sieve()
{
memset( prime, -1, sizeof( prime ) );
unsigned int i;
unsigned int sqrtN = ( unsigned int )sqrt( ( double )N ) + 1;
for( i = 3; i < sqrtN; i += 2 ) if( gP( i ) )
{
unsigned int i2 = i + i;
for( unsigned int j = i * i; j < N; j += i2 ) rP( j );
}
}
It is just the sieve implemented using a bitset.
Where have you found it?
Just look at binary representation. There are 1s at the places, where current odd number is prime. For example, prime[0] and corresponidng odd numbers:
as I can see this is space eficient code only
Sure. Actually, it's also a little bit (good joke, hah?) slower: in original sieve we just check if current cell of bool array is true, but here — 5 or 6 bit operations! =) Anyway, I think this idea isn't very useful... Yes, it's able to store 10^9 primes but it still can't fit in any reasonable TL.
Totktonada what will the final representation of the array prime be and since it contains size n/64 how will i check later if a number is prime from the sieve generated ? for example i have generated the sieve before and later i wish to check for primalty of prime number just less than the max value ie N. How will i check it ?
Totktonada when we finally complete the sieveing work with the array prime what we have is the array prime[]. how do we find if a number is prime or not from the array prime[]. ?
Should I repeat it again? =) Well, that's not hard:
Actually gP(x) <=> prime[n>>6]&(1<<((n>>1)&31)) depend on prime[]. A short explanation about what's going on:
We check n/2 because it will convert odd numbers to consectutive integers: 1,3,5,7... -> 0,1,2,3...
Let k=n/2; then in prime[k/32] we store (after sieve) some integer x, which contains at its binary representation 1 at position (k%32) iff k is a prime.
How to do it efficiently enough? Use binary tricks. n>>1 instead of n/2, k&31 instead of k%32, k>>6 instead of k/32. To get i-th bit of x: x&(1<<i). The only thing I added to checkPrime — check if x is even or not: (x&1)&&...
Here is a good example of use. The only problem: it counts 1 as prime also.
P.S. Or I misunderstood your question?
Wonderful. This is the first time I see someone use bitwise for sieving
how to use this anyway ? ;-;
[Deleted]