#include <iostream>
#include <fstream>
#include <algorithm>
#include <list>
#include <vector>
#include <cmath>
#include <cassert>

using namespace std;

class PrimeGenerator {
  public:
    PrimeGenerator() {
        normalSolution();
    }

    int nextPrime() {
        int p = m_primes.front();
        m_primes.pop_front();
        // https://e...content-available-to-author-only...a.org/wiki/Prime-counting_function
        // pi(m_size) > m_size / ln(m_size) for m_size >= 17 (which starts at 100 so its true)
        // pi(m_size / 4) <= 1.25506 * (m_size / 4) / ln(m_size / 4) <= 1.25506 * (m_size / 4) / ln(m_size ^ 0.5) = 1.25506 * (m_size / 2) / ln(m_size)
        // so the number of primes bigger than m_size / 4 but lower than or equal to m_size is
        // > m_size / ln(m_size) - 1.25506 * (m_size / 2) / ln(m_size) = m_size / ln(m_size) * 0.37247
        // so doSomeSteps is called at least m_size / ln(m_size) * 0.37247
        // and because doSomeSteps does O(ln(m_size)) operations and p > m_size / 4 it does O(ln p) operations
        if (p > m_size / 4)
            doSomeSteps();
        return p;
    }

  private:
    // iterator, meant to hold a state in normalSolution
    struct Iterator {
        int step; // 0 -> filling with 0, 1 -> doing the sieve, 2 -> removing primes
        int i;
        list<int>::iterator p;
    } m_iterator;

    void normalSolution() {
        m_size = START_SIZE;
        m_calls = ceil(log(m_size) * 43);
        m_lowest_prime = vector<int>(m_size + 1, 0);
        // Sieve of erathostenes in linear time,
        // this algorithm makes N + pi(N) + N operations, upper bounded by 3N
        // the if is true in pi(N) cases <= N
        // we update at most once each element => N operations
        // the for condition will have to break one for each element => N operations
        for (int i = 2; i <= m_size; ++i) {
            if (m_lowest_prime[i] == 0) {
                m_lowest_prime[i] = i;
                m_primes.push_back(i);
            }
            for (auto &prime : m_primes) {
                if (prime > m_lowest_prime[i])
                    break;
                if (i * prime > m_size)
                    break;
                m_lowest_prime[prime * i] = prime;
            }
        }
        m_lowest_prime_second = vector<int>(m_size * 4 + 1);
        m_iterator = {0, 0, m_primes_second.begin()};
    }

    // to do the sieve on 4 * m_size we need 16 * m_size operations
    // 4 * m_size to fill the array with 0
    // 8 * m_size to simulate the sieve in linear time
    // pi(m_size * 4) to remove the already printed primes, <= 4 * m_size
    // and we have at least m_size / ln(m_size) * 0.37247 calls, so to distribute them all
    // we need to do at least 16ln(m_size) / 0.37247 ~ 43 ln(m_size) which is O(ln(m_size))
    void doSomeSteps() {
        int operations = m_calls;
        for (int i = 0; i < operations; ++i)
            doStep();
        if (done())
            swap();
    }

    // complexity of this is O(1)
    void doStep() {
        if (m_iterator.step == 0) { // filling with 0, this will happen exactly 4 * m_size times
            m_lowest_prime_second[m_iterator.i++] = 0;
            if (m_iterator.i > m_size * 4)
                m_iterator = {1, 2, m_primes_second.begin()};
            return;
        }
        if (m_iterator.step == 1) { // doing the actual sieve
            // when its prime, this will be at most pi(4 * m_size) <= 4 * m_size
            if (m_lowest_prime_second[m_iterator.i] == 0) {
                m_lowest_prime_second[m_iterator.i] = m_iterator.i;
                m_primes_second.push_back(m_iterator.i);
                m_iterator.p = m_primes_second.begin();
                return;
            }
            // break condition, this will happen exactly 4 * m_size
            if (m_iterator.p == m_primes_second.end()
                || *m_iterator.p > m_lowest_prime_second[m_iterator.i]
                || *m_iterator.p * m_iterator.i > m_size * 4) {
                m_iterator = {1, m_iterator.i + 1, m_primes_second.begin()};
                if (m_iterator.i > 4 * m_size)
                    m_iterator = {2, 0, m_primes_second.end()};
            } else {
                m_lowest_prime_second[*m_iterator.p * m_iterator.i] = *m_iterator.p;
                m_iterator.p++;
            }
            return;
        }
        if (m_iterator.step == 2) { // removing primes
            if (m_primes_second.front() <= m_size)
                m_primes_second.pop_front();
            else
                m_iterator.step = 3;
            return;
        }
    }

    // when we have finished creating the second sieve (which is 4 times bigger) and exhausted the primes from the first
    bool done() {
        return m_iterator.step == 3 && m_primes.begin() == m_primes.end();
    }

    void swap() {
        ::swap(m_lowest_prime, m_lowest_prime_second);
        ::swap(m_primes, m_primes_second);
        m_size *= 4;
        m_calls = ceil(43 * log(m_size));
        m_lowest_prime_second = vector<int>(4 * m_size + 1);
        m_iterator = {0, 0, m_primes.begin()};
    }
    list<int> m_primes, m_primes_second;
    vector<int> m_lowest_prime, m_lowest_prime_second;
    int m_size, m_calls;

    static const int START_SIZE = 100;
};

vector<int> primes(int N) {
    vector<bool> sieve(N + 1, true);
    vector<int> primes;
    for (int i = 2; i * i <= N; ++i)
        if (sieve[i] == true) {
            for (int j = i * i; j <= N; j += i)
                sieve[j] = false;
        }
    for (int i = 2; i <= N; ++i)
        if (sieve[i] == true)
            primes.push_back(i);
    return primes;
}

vector<int> generator(int P) {
    vector<int> primes;
    PrimeGenerator G;
    while (P--)
        primes.push_back(G.nextPrime());
    return primes;
}

int main() {
    ios::sync_with_stdio(false);

    int N = 10 * 1000 * 1000;
    auto normalSieve = primes(N);
    auto smartGenerator = generator(normalSieve.size());
    assert(normalSieve == smartGenerator);
}