Karan2116's blog

By Karan2116, 5 years ago, ,

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 );
}
}


• +5

 » 5 years ago, # |   +7 It is just the sieve implemented using a bitset.
 » 5 years ago, # |   0 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: 1 1 1 1 0 1 1 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1 0 0 1 1 0 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 
•  » » 5 years ago, # ^ |   0 as I can see this is space eficient code only
•  » » » 5 years ago, # ^ |   0 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.
•  » » 5 years ago, # ^ |   0 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 ?
•  » » » 5 years ago, # ^ |   0 bool checkPrime (int x) {return (x&1)&&gP(x); } 
•  » » » » 5 years ago, # ^ |   0 Thanks
•  » » » » 5 years ago, # ^ |   0 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[]. ?
•  » » » » » 5 years ago, # ^ |   0 Should I repeat it again? =) Well, that's not hard: bool checkPrime (int x) {return (x&1)&&gP(x); } 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<
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 Also i found the code in a blog with reference to question TDKPRIME on spoj.
 » 6 weeks ago, # | ← Rev. 2 →   -8 Wonderful. This is the first time I see someone use bitwise for sieving
•  » » 6 weeks ago, # ^ |   0 how to use this anyway ? ;-;
•  » » » 6 weeks ago, # ^ |   0 typedef vector vi; vi prime; #define N 51000000 unsigned int flag[N / 64]; #define gP(n) (flag[n>>6]&(1<<((n>>1)&31))) #define rP(n) (flag[n>>6]&=~(1<<((n>>1)&31))) #define iP(n) ((n&1)&&gP(n)) void sieve() { int sqrtN = sqrt(N); for(int i = 3; i <= sqrtN; i += 2) if (gP(i)) for(int j = i * i; j < N; j += 2 * i) rP(j); prime.assign(1, 2); for (int i = 1; i < N; ++i) if (iP(i)) prime.push_back(i); } 
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   -13 [Deleted]