vector<bool> isPrime(N, true);

void sieve() {
    isPrime[0] = isPrime[1] = false;
    for (int i = 0; i < N / i; ++i) {
        if (isPrime[i])
            for (int j = i * i; j < N; j += i)
                isPrime[j] = false;
    }
}