#include <vector>
#include <utility>
#include <cmath>

using namespace std;

vector<uint64_t> erat(uint64_t N) {
    typedef std::pair<std::vector<char>::iterator, unsigned int> bit;

    auto do_step = [] (bit& b, uint64_t s) -> void {
        uint64_t dist = b.second + s;
        b.first += dist / 8u;
        b.second = dist % 8u;
    };

    auto is_prime = [] (const bit& b) -> bool {
        return static_cast<bool>(*(b.first) & (1 << b.second));
    };

    auto next_prime = [&do_step, &is_prime] (uint64_t& prime, bit& b) -> void {
        do {
            do_step(b, 1u);
            prime += 2u;
        } while (!is_prime(b));
    };

    auto make_false = [] (bit& b) -> void {
        *(b.first) &= ~(1 << b.second);
    };

    auto index = [] (uint64_t num) -> uint64_t {
        return (num - 3u) / 2u;
    };

    vector<char> bits(N / 16 + 1, -1);
    vector<uint64_t> primes({2});

    uint64_t p = 3;
    bit b(bits.begin(), 0u);
    auto max = static_cast<uint64_t>(sqrt(N)) + 1u;

    while(p < max) {
        bit comp(bits.begin(), 0u);
        do_step(comp, index(p * p));
        for (comp; comp.first < bits.end(); do_step(comp, p))
            make_false(comp);

        primes.push_back(p);
        next_prime(p, b);
    }

    while (b.first < bits.end()) {
        primes.push_back(p);
        next_prime(p, b);
    }

    while (*primes.rbegin() > N)
        primes.pop_back();

    return primes;
}