Karan2116's blog

Optimized Sieve
By Karan2116, 10 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

Comments Comments (12)
| Write comment?
»
10 years ago, # |
  Vote: I like it +7 Vote: I do not like it

It is just the sieve implemented using a bitset.

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

    as I can see this is space eficient code only

    → Reply
    • »
      »
      »
      10 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.

      → Reply
  • »
    »
    10 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 ?

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

        → Reply
        • »
          »
          »
          »
          »
          10 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?

          → Reply
»
5 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

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

    how to use this anyway ? ;-;

    → Reply
    • »
      »
      »
      5 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);
}
      → Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it -13 Vote: I do not like it

    [Deleted]

    → Reply