One of the most popular prime number algorithm is the Sieve which comes handy when you are required to generate prime numbers up to an upper bound.In this post we’ll be optimizing sieve to save both memory as well as time.

The optimization that we’ll be performing will be both memory as well as time efficient.

**NOTE – **I won’t be discussing how the basic sieve works.(Check out – Sieve(without optimisation)).

We will move step by step towards optimizing the algorithm to maximum extent.(If you know any further optimizations, please do share in the comment box).

So here’s what sieve looks like without any optimization.

//============================================================================ // Name : sieve.cpp // Author : Prateek Agarwal // Institution : NIT Jalandhar //============================================================================ #include <bits/stdc++.h> using namespace std; #define MAX 1000000 #define SQ 1000 int prime[MAX+1]; int sieve(){ for (int i=2;i<=SQ;i++){ if (!prime[i]){ for(int j=i*i;j<=MAX;j+=i){ prime[j] = 1; } } } return 0; } int main(){ sieve(); return 0; }

Lets begin our optimization!

Considering that you are processing the algorithm for 1000 elements, the size of the array is 4000 bytes (4 bytes or 32 bits per int value).

Instead of using an entire integer(32 bits) for marking as prime(or composite) , you could use just 1 bit.How?

use array index ‘0’ to store values for the first 32 (from 1 to 32) numbers, index ‘1’ for the next 32 (from 33 to 64) numbers and so on..

This will save us a lot of memory.But still there’s no improvement in time.

**Just don’t consider the even values at all.**This will make your algorithm faster by a factor of 2 or more.

Now all we have are odd values to deal with.Lets see what the arrangement will look like after neglecting the even values.

This not only speeds up your algorithm, but saves even more memory.(Now we are using 4000/64 = 62.5 bytes of memory).

So here’s the code for the complete optimization and later we’ll see how the bit wise magic is working.

//============================================================================ // Name : optimised_bitwise_sieve.cpp // Author : Prateek Agarwal // Institution : NIT Jalandhar //============================================================================ #include <bits/stdc++.h> using namespace std; #define MAX 100000000 #define SQ 10000 //These macros are discussed below #define check(n) (prime[n>>6]&(1<<((n&63)>>1))) #define set(n) prime[n>>6]|=(1<<((n&63)>>1)) int prime[MAX>>6]; int sieve(){ for(int i=3;i<=SQ;i+=2){ if (!check(i)){ int inc = 2*i; for(int j=i*i;j<=MAX;j+=inc){ set(j); } } } return 0; } int main(){ sieve(); return 0; }

Let us see how we can access and modify the bit value for a number ‘n’ (n is odd) .

- Get the array index where the bit value of ‘n’ is stored. Since we are storing the bit values of 32 consecutive odd numbers in one integer , the array index can be generalized as
**n/64**or**n>>6**. So the array value if**prime[n>>6]**. - Now in order see which bit to visit,we have to modulo by
**64**and then divide by**2**.Example – numbers 1 and 65 in the picture above both have their result stored in first (least significant) bit but in different indexes. If we modulo both of them by**64**,we will get**1**and then divide by**2**, we will get**0**which is the required bit position. - the modulo operation
**n%64**can be seen as**n&63**. This is similar to what happens when we divide a number(in base 10) by**10^k**. We get the last**k**digits of that number.Except this time the modulo operation is taking place in**base 2**. So if we modulo**n**number by**2^6**, we will get the last**6**digits in the**base 2**representation of**n.**(which is**n&63**).Try it out yourself for further clarification.

So to sum up, the first point gives us the logic for the array index in which the bit value for **n** is present – **prime[n>>6]**

And second and third points combined tells us about the bit position given by – **((n&63)>>1)**

Now we can check as well as set the bit values.

Hope you understood the post 🙂

Here’s a question on optimized bit wise sieve (where normal sieve won’t work) on SPOJ-TDKPRIME.

Please explain the statement “use index 0 to store values of first 32 numbers and index 1 to store next 32 numbers “.

LikeLike

Since an integer has 32 bits, each bit can be used as a hash for a number (instead of using an entire array index as hash)

For eg- Normal hashing is done like this

Hash[0] = 0 or 1 (indicates hash value for 0)

Hash [1] = 0 or 1(indicates hash value for 1)….. And so on

Here, since 0 and 1 are only possible values to store(which can be done by setting a bit on or off)

An integer (Hash[i] having 32bits) can store the hash values for 32 different integers.

Refer the image for clarity

LikeLike

Thanks for your response. But still with reference to your image the number 63 is set off (not prime) and 61 59 are set off (prime). Please elaborate.

LikeLike

Ya that’s a mistake. 63 was supposed to be on (composite)

LikeLike