Compute primes upto n

primes.cpp

/* really fast & efficient, if you need to increase speed replace std::vector by std::list */
#include <cmath>
#include <list>
#include <vector>
#include <iostream>

using namespace std;

vector<int> getPrimes(int n) {
    vector<bool> crible(n + 1, true);
    vector<int> primes;

    primes.push_back(2);

    int max = static_cast<int>(floor(sqrt(static_cast<double>(n)))) + 1;

    for(int i = 3; i < max; i += 2) {
        if(crible[i]) {
            primes.push_back(i);

            int borneSup = n / i;

            for(int j = i; j <= borneSup; j += 2) {
                crible[i * j] = false;
            }
        }
    }

    int min = max % 2 == 0 ? max + 1 : max;

    for(int i = min; i <= n; i += 2) {
        if(crible[i]) {
            primes.push_back(i);
        }
    }

    return primes;
}

int main(int arcg, char **argv) {
    cout << getPrimes(1000000000).size() << endl;
    return 0;
}