#include <iostream>
#include <vector>
using namespace std;

// Hàm sàng nguyên tố - sử dụng Sieve of Eratosthenes để tìm tất cả các số nguyên tố <= 3*n
vector<bool> sieve(int maxN) {
    vector<bool> is_prime(maxN + 1, true);

    is_prime[0] = is_prime[1] = false;  // 0 và 1 không phải là số nguyên tố

    for (int i = 2; i * i <= maxN; i++) {
        if (is_prime[i]) {
            for (int j = i * i; j <= maxN; j += i) {
                is_prime[j] = false;  // Đánh dấu các bội số của i là không phải số nguyên tố
            }
        }
    }

    return is_prime;  // Trả về mảng đánh dấu số nguyên tố
}

// Hàm tìm và in các cặp (x, y) sao cho x + 2*y là số nguyên tố
void findValidPairs(int n, const vector<bool>& is_prime) {
    for (int x = 1; x <= n; x++) {
        for (int y = 1; y <= n; y++) {
            int sum = x + 2 * y;
            if (sum <= is_prime.size() && is_prime[sum]) {
                cout << "(" << x << ", " << y << ") -> x + 2*y = " << sum << " là số nguyên tố" << endl;
            }
        }
    }
}

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

    // Giới hạn tối đa để kiểm tra số nguyên tố cho biểu thức x + 2*y là 3*n
    int maxSum = 3 * n;

    // Gọi hàm sàng nguyên tố cho các số từ 0 đến maxSum
    vector<bool> is_prime = sieve(maxSum);

    // Tìm các cặp (x, y) sao cho x + 2*y là số nguyên tố
    cout << "Các cặp (x, y) thỏa mãn điều kiện là: " << endl;
    findValidPairs(n, is_prime);

    return 0;
}