Untitled

const int N = 1e5;

// sieve prime, careful with int overflow

vector <int> primes;
vector <bool> isPrime(N + 5, true);

void sieve() {
    isPrime[0] = isPrime[1] = false;
    for (int i = 4; i <= N; i += 2) {
        isPrime[i] = false;
    }

    for (int i = 3; i * i <= N; i += 2) {
        if (isPrime[i]) {
            for (int j = i * i; j <= N; j += i * 2) {
                isPrime[j] = false;
            }
        }
    }

    primes.push_back(2);
    for (int i = 3; i <= N; i += 2) {
        if (isPrime[i]) {
            primes.push_back(i);
        }
    }
}