sieve_of_eratosthenes.cpp

std::vector<int> get_primes(int limit)
{
    std::vector<char> primes(limit, 1);
    std::vector<int> final;

    // 0 and 1 are nonprime by definition
    primes[0] = 0; primes[1] = 0;

    for (int i = 2; i * i <= limit; i++)
    {
        if(primes[i])
        {
            // pushes back any prime below sqrt(limit)
            final.push_back(i);

            for (int j = i * i; j <= limit; j+= i)
            {
                primes[j] = 0;
            }
        }
    }

    // now we loop over all primes we've found over sqrt(limit)
    for (int k = (int)floor(sqrt((limit))) + 1; k <= limit; k++ )
    {
        if(primes[k])
        {
            final.push_back(k);
        }
    }

    return final;
}