#include <iostream>
#include <string>
#include <vector>

class Sieve {
private:
    std::string sieve;

public:
    // Constructor to initialize sieve with 'P' (prime assumption)
    Sieve(size_t limit) : sieve(limit + 1, 'P') {
        // 0 and 1 are not primes
        sieve[0] = 'C';
        if (limit > 0) sieve[1] = 'C';

        // Sieve of Eratosthenes
        for (size_t i = 2; i * i <= limit; ++i) {
            if (sieve[i] == 'P') {
                for (size_t j = i * i; j <= limit; j += i) {
                    sieve[j] = 'C';
                }
            }
        }
    }

    // Get primes as a vector of integers
    std::vector<int> getPrimes() const {
        std::vector<int> primes;
        for (size_t i = 2; i < sieve.size(); ++i) {
            if (sieve[i] == 'P') {
                primes.push_back(i);
            }
        }
        return primes;
    }

    // Print all primes in the range
    void printPrimesInRange(int start, int end) const {
        for (int i = start; i <= end; ++i) {
            if (sieve[i] == 'P') {
                std::cout << i << " ";
            }
        }
        std::cout << std::endl;
    }

    // Get the largest prime below a limit
    int largestPrimeBelow(int limit) const {
        for (int i = limit; i >= 2; --i) {
            if (sieve[i] == 'P') {
                return i;
            }
        }
        return -1; // If no prime is found
    }
};

// Main function for testing
int main() {
    const int limit = 100000;

    // Create a Sieve instance for the range 0 to limit
    Sieve sieve(limit);

    // Print primes between 1 and 200
    std::cout << "Primes between 1 and 200:" << std::endl;
    sieve.printPrimesInRange(1, 200);

    // Find and print the largest prime below 100,000
    int largestPrime = sieve.largestPrimeBelow(limit);
    std::cout << "Largest prime below " << limit << ": " << largestPrime << std::endl;

    return 0;
}