#include <bits/stdc++.h>

using namespace std;

// Global vector that will hold the primality status of each number up to n‑1
vector<bool> isPrime;

// Sieve of Eratosthenes – marks all composite numbers up to n‑1 as false
void sieveOfEratosthenes(int n) {
    // Initialise the vector: assume every number is prime initially
	isPrime = vector<bool>(n, true);

	// 0 and 1 are not prime by definition
	isPrime[0] = false;
	isPrime[1] = false;

	// Only need to iterate up to √n; any non‑prime > √n will have a factor ≤ √n
	int limit = static_cast<int>(sqrt(n));

	// Examine each candidate i
    for (int i = 2; i <= limit; ++i) {
        // If i is still marked prime, eliminate its multiples
        if (isPrime[i]) {
            // Start from i*i (smaller multiples were already crossed out by smaller factors)
            for (int j = i * i; j <= n; j += i) {
                isPrime[j] = false; // Mark j as composite
            }
        }
    }
}