Data Structure and Algorithm - Sieve of Eratosthenes

Just have some fun to implement this small algorithm from wikipedia http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes, when I was way back home on the train from work.

As this wiki page stated, this algorithm takes O(n) memory, it won't be memory-efficient when n is large. It will be difficult  to allocate such a big size for "flags". Good thing is that std::vector<bool> is actually bit-base implementation, which means each bool only takes one bit. This is not a bad thing for this case.

As C++11 comes into force, now we can return an instance of anything of std::vector, because of the newly introduced move constructor. No more worries about the efficiency of return value and no more dependent on the optimization of compilers.

The following code is to compute all the prime numbers under a given number "n".
------------------------------------------------------------------------------------------------------------
#include <vector>

using namespace std;

vector<size_t> SieveOfEratosthenes(size_t n)
{
    if (n < 2) {
        return vector<size_t>();
    }

    vector<size_t> result;
    result.reserve(n>>1));
    result.push_back(2);
    vector<size_t> flags((n>>1)- 1, true); // 3, 5, 7  
    size_t p;
    for (size_t i = 0; i < flags.size(); ++i) {
        if (flags[i]){
            p = (i << 1) + 3;
            for (size_t j = p*p; j < n; j+=(2*p)) {
                flags[(j-3) >> 1] = false;
            }
            result.push_back(p);
        }
    }

    return result;
}