[Tapas Bose]

Thank you very much for your explanation sir NickDMax specially for bit-shift. I think I understand the logic of your code and bit-shift operation. I re-implemented your code using bitset instead of char (as a task and for self-assessment. Undoubtedly this forum and sir like you, baavgai, Ferencn, r.stiltskin, Martyn.Rae, sarmanu and many other helps me and others a lot to know the language properly. I am expressing my gratitude towards you.).
Here is the code, although it is not as much as fast than your one. It's just a try :

#include <iostream>
#include <limits>
#include <bitset>

using namespace std;

class BigBitSet {
	private :
	bitset<32> *bits;
	public:
	typedef unsigned long long int size_t;
    
	explicit BigBitSet(BigBitSet::size_t size) : bits(NULL) {
		BigBitSet::size_t  arraySize = size / 32;
        
		if (arraySize > numeric_limits<std::size_t>::max()) {
			cout << "  Array size is TOO big to allocate." << endl;
		}
        
		try {
			bits = new bitset<32>[size_t(arraySize)];
		}
		catch(bad_alloc &) {
			cout <<"Array did not allocate." << endl;
			abort();
		}
	}
    
	~BigBitSet() {
		if (bits) { 
			delete bits; 
		}
		
		bits = NULL;
	}
    
	inline BigBitSet& set(BigBitSet::size_t index) {
		std::size_t byte = index / 32;
		std::size_t bit = index % 32; 
		bits[byte] |= 1 << bit;
		return *this; 
	}
    
	inline BigBitSet& unset(BigBitSet::size_t index) {
		std::size_t byte = index / 32;
		std::size_t bit = index % 32;
		bits[byte] &= ~(1 << bit);
		return *this;
	}

	inline int get(BigBitSet::size_t index) const {
		std::size_t byte = index / 32;
		std::size_t bit = index % 32;
		return bits[byte][bit];
	}
};

const unsigned long long int Limit = 10000000000ULL;
const unsigned long long int SqrtLimit = 100000ULL;
const unsigned long long int ReportDepth = SqrtLimit / 100;
const unsigned long long int ReportAt = ReportDepth - 1;
const unsigned long long int FiftyBillion = 500000000ULL;

int main() {
	BigBitSet isPrime(Limit);
    
	cout << "  Memory allocated." << endl;
	cout << "  Initialization begin";
	
	isPrime.unset(0);
	isPrime.unset(1);
	isPrime.set(2);
	isPrime.set(3);
	
	for(BigBitSet::size_t i = 4; i < Limit; i++) {
		if (i & 1) {
			isPrime.set(i);
		}
		else {
			isPrime.unset(i);
		}
		
		if (i % FiftyBillion == 0) {
			(cout << ".").flush();
		}
	}
	
	cout << endl;
	cout << "  Initialization done." << endl;	
	cout << "  Calculation begin";

	for(BigBitSet::size_t i = 3; i < SqrtLimit; i += 2) {
		if (i % ReportDepth == ReportAt) { 
			(cout << ".").flush(); 
		}
		
		if (isPrime.get(i)) { 
			for(BigBitSet::size_t j = i * i; j < Limit; j += i) {
				isPrime.unset(j);
			}
		}
	}

	cout << endl;
	cout << "  Done Calculation." << endl;
	cout << "  Counting begin"; 
	BigBitSet::size_t count = 1;
           
	for(BigBitSet::size_t i = 3; i < Limit; i += 2) {
		if (isPrime.get(i)) {
			count++;
		}
		
		if (i % FiftyBillion == 1) {
			(cout << ".").flush();
		}
	}
	
	cout << endl;
	cout << "  Calculated " << count << " primes upto " << Limit << endl;
    
	return 0;
}

In this post you instructed me to optimize my code, and I try it (this is also not fast enough):

#include <iostream>
#include <vector>
#include <cmath>
#include <ctime>
#include <cstdlib>

using namespace std;

class SieveOfEratosthenes {
	private :
	vector<bool> *isPrime;
	//bool **isPrime;
	unsigned long long int Limit;
	unsigned long long int sqrtLimit;
	unsigned long long int ReportDepth;
	unsigned long long int ReportAt;
	unsigned long long int FiftyBillion;	
	unsigned long long int row;
	unsigned long long int col;
	
	
	public :
	explicit SieveOfEratosthenes(unsigned long long int lim) : Limit(lim) {
		sqrtLimit = (unsigned long long int)sqrt(Limit);		
		row = 10ULL;
		col = Limit / row;
		ReportDepth = sqrtLimit / 100;
		ReportAt = ReportDepth - 1;
		FiftyBillion = 500000000ULL;
		
		cout << "  Initializing " << endl;
		
		try {
			isPrime = new vector<bool>[row];
			
			for (int i = 0; i < row; i++) {
				isPrime[i].resize(col, true);
			}
			
			//isPrime = new bool *[row];
			
			/*for (int i = 0; i < row; i++) {
				isPrime[i] = new bool[];
			}*/
		}
		catch (bad_alloc &) {
			cout << "  Initialization failed." << endl;
			abort();
		}
		cout << "  Initialization done." << endl;
	}
	
	~SieveOfEratosthenes() {
		delete[] isPrime;
		isPrime = NULL;
	}
		
	inline void set(unsigned long long int index, bool val) {
		isPrime[index / col][index % col] = val;
	}
	
	inline bool get(unsigned long long int index) {
		return isPrime[index / col][index % col];
	}
	
	void primegen() {		
		cout << "  Prime computation started";
		
		isPrime[0][0] = false;
		isPrime[0][1] = false;
		
		for (unsigned long long int i = 2; i < sqrtLimit; i++) {
			if (get(i)) {
				for (unsigned long long int j = i * i; j < Limit; j += i) {
					set(j, false);
				} 
			}
			
			if (i % ReportDepth == ReportAt) { 
				(cout << ".").flush(); 
			}
		}
		
		cout << endl;
		cout << "  Prime computation end." << endl;
	}

	void primecount() {
		cout << "  Prime count started";
		unsigned long long int count = 0;
		
		for (unsigned long long int i = 0; i < Limit; i++) {
			if (get(i)) {
				count++;
			}
			
			if (i % FiftyBillion == 1) {
				(cout << ".").flush();
			}
		}
		
		cout << endl;
		cout << "  Prime count end." << endl;		
		cout << "  Total number of prime upto " << Limit << " : " << count << endl;
	}
};

int main() {
	SieveOfEratosthenes Prime(10000000000ULL);

	Prime.primegen();
	Prime.primecount();
	
	return 0;
}

According to the runtime comparison the first code(1600 sec) is faster than second one(real 2500 sec).
I will wait for your response sir.

[NickDMax]

ummmmmm... I don't think you properly replaces char with bitset... to set/unset in the bitset you would do something like:

        BigBitSet& set(BigBitSet::size_t index) {
                std::size_t byte = index / 32;
                std::size_t bit = index % 32; 
                bits[byte][bit] = true;
                return *this; 
        }

BTW: You don't need the keyword "inline" when you put code into the class declaration -- any code inside the class declaration is assumed to be "inline" by the compiler. If you don't want it inline then you have to declare it inside the class, but define it outside. Just FYI.

As for your program -- well for this approach I don't know how better to optimize really... since you are using the vector array you could create a concurrent version.

Start by doing the sieve on the first vector. Limit/ 10 = 1000000000 is MUCH smaller than sqrt(Limit) (for large values of Limit anyway) so you will have all primes less than sqrt(Limit). You can then use those values in check off all the non-primes in the remaining 9 vectors independently (1 thread per vector).

IF you are using VS2010 you might take a look at the new Concurrency Runtime (though I would probably use the Boost::Thread myself because I have not quite wrapped my head around the Concurrency Runtime).

ON my computer your version finished its calculation in 868.592 seconds -- so it is kind of slow -- my only other suggestion would be to ditch the vector (which is what I did with my BigBitSet class)

[Tapas Bose]

Yes sir you are right, thats a fault. I am in Ubuntu. I saw in your code, that you are using <boost/thread.hpp>. Then I took a look on boost::thread, but don't understand how to use it in my code. Can you give any suggestion? I saw while executing the code there are some pause between two operations, I mean after the completion of initialization, it takes some time to print "computation begin" also after computation it pause for some moment before initiating counting. What is the reason behind this behavior sir?

[NickDMax]

cout << " Prime computation started"; <-- nothing to flush the buffer... try
(cout << " Prime computation started").flush();
or
cout << " Prime computation started" << endl;

sorry that #include <boost/thread.hpp> should not have been there. I was just trying to see if I had everything hoked up correctly to run the code (I do not, I need to rebuild boost::thread for VS2010 but I have a problem that I have not found a solution for yet).

using boost::thread is really not all that hard. You will need to make some functions that take a constant reference to the isPrime[0] vector (it needs to be a constant reference because you cannot update isPrime[0] while the other threads are using it, that would require locking and we want to avoid all of that nonsense.) and a reference to the target vector, and probably the bounds for that vector so something like:

void workerFunction(const vector<bool>& primes, vector<bool> isPrime, Sieve::size_t min, Sieve::size_t max);

where min and max are the bounds for that particular vector.

From there you create a thread object using that function:

boost::thread workerThread(workerFunction, isPrime[0], isPrime[n], (Limit/10)*n,(Limit/10)*(n+1)-1);

please not this is all "off the cuff" so I don't know how accurate the above is... but it is the basic process.

See here for a basic example of how to create threads.