Cerința

Se consideră un șir cu n numere naturale. Determinați cel mai lung subșir crescător al șirului, cu proprietatea că toate elementele subșirului sunt numere prime. Dacă există mai multe subșiruri de lungime maximă să va afișa subșirul minim lexicografic.

Date de intrare

Fișierul de intrare sclmprime.in conține pe prima linie numărul n, iar pe a doua linie n numere naturale separate prin spații.

Date de ieșire

Fișierul de ieșire sclmprime.out va conține pe prima linie numărul m, reprezentând lungimea maximă a unui subșir crescător de numere prime. A doua linie va conține m numere prime (separate prin spații) ce reprezintă subșirul crescător de lungime maximă de numere prime. În cazul în care sunt mai multe subșiruri de lungime maximă se va scrie subșirul minim lexicografic.

Restricții și precizări

• 1 ≤ n ≤ 1000
• numerele de pe a doua linie a fișierului de intrare vor fi mai mici decât 1.000.000

Exemplu

sclmprime.in

10
5 10 2 4 5 8 9 8 11 7

sclmprime.out

3
2 5 7

Explicație

Lungimea maximă a unui subșir crescător de numere prime este 3.
Se observă că sunt mai multe subșiruri de lungime 3: 5 5 11; 5 5 7; 2 5 11; 2 5 7.
Cel mai mic din punct de vedere lexicografic este subșirul: 2 5 7.

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

ifstream cin("sclmprime.in");
ofstream cout("sclmprime.out");

int n , a[1002] , L[1002] , l , lmax , ne , b;

int prim(int n)
{
    if(n == 0 || n == 1) return 0;
    else if(n == 2) return 1;
    else if(n % 2 == 0) return 0;
    else for(int i = 3 ; i * i <= n ; i += 2)
        if(n % i == 0) return 0;
    return 1;
}

int main()
{
    cin >> ne;
    for(int i = 1 ; i <= ne ; i++)
    {
        cin >> b;
        if(prim(b)) a[++n] = b;
    }
    L[n] = 1;
    for(int i = n ; i >= 1 ; i--)
    {
        L[i] = 1;
        for(int j = i + 1 ; j <= n ; j++)
            if(a[i] <= a[j] && L[i] < L[j] + 1)
                L[i] = L[j] + 1;
        if(L[i] > lmax) lmax = L[i];
    }
    cout << lmax << '\n';
    int poz = 0 , mini = 2000000000 , lpoz = 0;
    a[lpoz] = -1 ;
    for(int k = lmax ; k > 0 ; k--)
    {
        mini = 2000000000;
        for(int i = lpoz + 1 ; i <= n ; i++)
            if(L[i] == k && a[i] < mini && a[i] >= a[lpoz])
                {
                    mini = a[i];
                    poz = i;
                }
        cout << a[poz] << " ";
        lpoz =poz;
    }
    return 0;
}