#include <iostream>
#include <vector>

using namespace std;

vector<int> sieveOfEratosthenes(int n) {
    vector<bool> isPrime(n, true);
    vector<int> primes;

    for (int p = 2; p * p < n; ++p) {
        if (isPrime[p]) {
            for (int i = p * p; i < n; i += p) {
                isPrime[i] = false;
            }
        }
    }

    for (int p = 2; p < n; ++p) {
        if (isPrime[p]) {
            primes.push_back(p);
        }
    }

    return primes;
}

int main() {
    int n;
    cout << "Nhập n: ";
    cin >> n;

    vector<int> primes = sieveOfEratosthenes(n);

    int largest1 = 0, largest2 = 0;

    for (int i = primes.size() - 1; i >= 0; --i) {
        if (primes[i] < n) {
            largest1 = primes[i];
            break;
        }
    }

    for (int i = primes.size() - 1; i >= 0; --i) {
        if (primes[i] < largest1) {
            largest2 = primes[i];
            break;
        }
    }

    cout << "Hai số nguyên tố lớn nhất bé hơn " << n << " là: " << largest1 << " và " << largest2 << endl;

    return 0;
}