#include <stdio.h>
#include <math.h>

int a[20], n;

void nhap() {
    do {
        printf("Nhap so luong phan tu (1-20): ");
        scanf("%d", &n);
    } while (n <= 0 || n > 20);

    for (int i = 0; i < n; i++) {
        printf("a[%d] = ", i);
        scanf("%d", &a[i]);
    }
}

int laChinhPhuong(int x) {
    if (x < 0) return 0;
    int k = sqrt(x);
    return k * k == x;
}

int laNguyenTo(int x) {
    if (x < 2) return 0;
    for (int i = 2; i <= sqrt(x); i++)
        if (x % i == 0) return 0;
    return 1;
}

void chinhPhuongChanLonNhat() {
    int found = 0, max;
    for (int i = 0; i < n; i++) {
        if (a[i] % 2 == 0 && laChinhPhuong(a[i])) {
            if (!found || a[i] > max) {
                max = a[i];
                found = 1;
            }
        }
    }
    if (found)
        printf("1. Chinh phuong chan lon nhat: %d\n", max);
    else
        printf("1. Khong co chinh phuong chan\n");
}

void demNguyenToLonNhat() {
    int max = -1, dem = 0;
    for (int i = 0; i < n; i++)
        if (laNguyenTo(a[i]) && a[i] > max)
            max = a[i];

    if (max == -1) {
        printf("2. Khong co so nguyen to\n");
        return;
    }

    for (int i = 0; i < n; i++)
        if (a[i] == max) dem++;

    printf("2. So nguyen to lon nhat: %d, so lan: %d\n", max, dem);
}

void chenNguyenToDauTien() {
    int k, value = -1;
    for (int i = 0; i < n; i++)
        if (laNguyenTo(a[i])) {
            value = a[i];
            break;
        }

    if (value == -1) {
        printf("3. Khong co so nguyen to de chen\n");
        return;
    }

    do {
        printf("Nhap k (0 <= k < %d): ", n);
        scanf("%d", &k);
    } while (k < 0 || k >= n);

    for (int i = n; i > k; i--)
        a[i] = a[i - 1];
    a[k] = value;
    n++;

    printf("3. Mang sau khi chen:\n");
    for (int i = 0; i < n; i++)
        printf("%d ", a[i]);
    printf("\n");
}

void sapXepTheoDe() {
    int b[20], idx = 0;

    for (int i = 0; i < n; i++)
        if (laChinhPhuong(a[i]))
            b[idx++] = a[i];

    for (int i = 0; i < idx - 1; i++)
        for (int j = i + 1; j < idx; j++)
            if (b[i] > b[j]) {
                int t = b[i]; b[i] = b[j]; b[j] = t;
            }

    for (int i = 0; i < n; i++)
        if (!laChinhPhuong(a[i]))
            b[idx++] = a[i];

    for (int i = 0; i < n - 1; i++)
        for (int j = i + 1; j < n; j++)
            if (!laChinhPhuong(b[i]) && !laChinhPhuong(b[j]) && b[i] < b[j]) {
                int t = b[i]; b[i] = b[j]; b[j] = t;
            }

    for (int i = 0; i < n; i++)
        a[i] = b[i];

    printf("4. Mang sau khi sap xep:\n");
    for (int i = 0; i < n; i++)
        printf("%d ", a[i]);
    printf("\n");
}

int main() {
    nhap();
    chinhPhuongChanLonNhat();
    demNguyenToLonNhat();
    chenNguyenToDauTien();
    sapXepTheoDe();
    return 0;
}