Sieve of Erathronese using Byte Array

(bit manipulation)

 Sieve of erathronese is a easy marking technique for finding prime numbers in less time.Using byte array for checking and marking of prime numbers increases space complexity as well as time complexity (as bit manipulations are fast). Using byte array 1 integer can be used to store 32 numbers.

Following code prints prime numbers upto 32000:

#include <iostream>
 
int arr[10000];
#define set(i) (arr[i>>5]|=(1<<(i&31)))
#define is_compound(i) (arr[i>>5]&(1<<(i&31)))

using namespace std;

int main()
{
    for(int i=3;i<32000;i+=2)
    {
        if(!is_compound(i))
        {
            int k=2*i;
            for(int j=i*i;j<32000;j+=k) set(j);
        }
    }

    cout<<2<<" ";
    for(int i=3;i<32000;i+=2) if(!is_compound(i)) cout<<i<<" ";
    cout<<endl;
}

Code is pretty straightforward. We have skipped even numbers for increasing time complexity.