Karan2116's blog

By Karan2116, 9 years ago, In English

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 ); } }
  • Vote: I like it
  • +5
  • Vote: I do not like it

| Write comment?
»
9 years ago, # |
  Vote: I like it +7 Vote: I do not like it

It is just the sieve implemented using a bitset.

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    as I can see this is space eficient code only

    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 ?

    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      bool checkPrime (int x) {return (x&1)&&gP(x); }
      
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like 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[]. ?

        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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:

          1. We check n/2 because it will convert odd numbers to consectutive integers: 1,3,5,7... -> 0,1,2,3...

          2. 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.

          3. 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?

»
4 years ago, # |
Rev. 2   Vote: I like it -8 Vote: I do not like it

Wonderful. This is the first time I see someone use bitwise for sieving

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    how to use this anyway ? ;-;

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      typedef vector<int> 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);
      }
      
  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it -13 Vote: I do not like it

    [Deleted]