#include <bitset>
#include <iostream>
#include <vector>

template <std::size_t N>
struct prime_sieve
{
    prime_sieve() : _sieve()
    {
        _sieve.flip();
        
        for (std::size_t i = 0; i < N; ++i)
        {
            if (_sieve.test(i))
            {
                auto value = 3 + i * 2;
                for (std::size_t j = i + value; j < N; j += value)
                    _sieve.reset(j);
            }
        }
    }

    std::vector<unsigned long long> get_primes() const
    {
        std::vector<unsigned long long> primes(1, 2);
        for (std::size_t i = 0; i < N; ++i)
            if (_sieve.test(i))
                primes.push_back(3 + i * 2);

        return primes;
    }

private:
    std::bitset<N> _sieve;
};


int main()
{
    const std::size_t bits = 4000;

    prime_sieve<bits> sieve;

    auto primes = sieve.get_primes();

    std::cout << "Found " << primes.size() << " primes using " << bits / 8 << " bytes.\n";
    std::cout << "Last prime found: " << primes.back() << '\n';
}