# PBinfo #2086 – SCLMprime – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: andrei

## Enunț

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ă se 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.

## Cod sursă C++

```cpp
# include <iostream>
# include <cstdio>
# include <climits>
# define maxn 1002
# define N_Max 1000010
using namespace std;
int x[maxn],L[maxn],Nr[maxn],N,k,lgmax,Min,poz,p,n;
bool prime[N_Max];
void ciur()
{
    int i,j;
    prime[0]=prime[1]=1;
    for(i=2; i<=N_Max; ++i)
    {
        if(prime[i]==0)
        {
            for(j=2; i*j<=N_Max; ++j)
                prime[i*j]=1;
        }
    }
}
int main()
{
    int i,j,y;
    freopen("sclmprime.in","r",stdin);
    freopen("sclmprime.out","w",stdout);
    ciur();
    scanf("%d", &n);
    for(i=1; i<=n; ++i)
    {
        scanf("%d", &y);
        if (!prime[y]) {
            x[++N] = y;
        }
    }
    L[N] = 1; lgmax = 1;
    for (i = N-1; i>0; --i)
    {
        L[i] = 1;
        for (j=i+1; j<=N; ++j)
            if (L[i]< 1 + L[j] && x[i]<=x[j])
            {
                L[i] = 1 + L[j];
            }
        if (L[i] > lgmax) lgmax = L[i];
    }
    printf("%d\n",lgmax);
    poz = 0;
    for(k = lgmax; k>0; --k)
    {
        Min = INT_MAX;
        for(i = poz+1; i <= N-k+1; ++i)
            if (Min > x[i] && L[i] == k && x[i] >= x[poz])
                p = i, Min = x[i];
        poz=p;
        printf("%d ",x[p]);
    }
    printf("\n");
    return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/2086)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/2086/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-2086/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)