#include <bits/stdc++.h>
using namespace std;

bool check(long long x) {
    if (x <= 1) return false;
    for (long long i = 2; i <= sqrt(x); ++i)
        if (x % i == 0) return false;
    return true;
}

int main() {
    long long n;
    cin >> n;
    vector<long long> a(n);
    for (long long i = 0; i < n; ++i) {
        cin >> a[i];
    }

    vector<long long> p;
    for (long long i = 0; i < n; ++i) {
        if (check(a[i])) {
            p.push_back(a[i]);
        }
    }


    long long m = p.size();
    vector<long long> dp(m, 1);
    vector<long long> prev(m, -1);

    long long mx = 1;
    long long mi = 0;

    for (long long i = 1; i < m; ++i) {
        for (long long j = 0; j < i; ++j) {
            if (p[i] > p[j] && dp[i] < dp[j] + 1) {
                dp[i] = dp[j] + 1;
                prev[i] = j;
            }
        }
        if (dp[i] > mx) {
            mx = dp[i];
            mi = i;
        }
    }

    vector<long long> lis;
    for (long long i = mi; i >= 0; i = prev[i]) {
        lis.push_back(p[i]);
        if (prev[i] == -1) break;
    }

    reverse(lis.begin(), lis.end());

    for (long long num : lis) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}

Đáp án:

Giải thích các bước giải: