#include <iostream>
#include <bitset>
using namespace std;
long long _sieve_size;
bitset<10000010> bs;
vector<int> primes;
//10^7 should be enough for most cases
void sieve(long long upperbound) {
    _sieve_size = upperbound + 1;
    bs.set();
    bs[0] = bs[1] = 0;
    for (long long i = 2; i <= _sieve_size; i++)
        if (bs[i]) {
        for (long long j = i * i; j <= _sieve_size; j += i) bs[j] = 0;
        primes.push_back((int)i);
    }
}