# PBinfo #3912 – PermPrimeVec – Rezolvare C++

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

## Enunț

Cerința
Se dă o mulțime cu n elemente, numere naturale. Afișați în ordine lexicografică toate permutările mulțimii date în care nu există două elemente prime alăturate.

Date de intrare
Programul citește de la tastatură numărul n și apoi n numere naturale, reprezentând elementele mulțimii.

Date de ieșire
Programul va afișa pe ecran permutările cerute, câte una pe fiecare rând și având elementele separate prin câte un spaţiu.

Restricții și precizări

1 < n ≤ 11
numărul valorilor prime din șir va fi aproximativ egal cu cel al valorilor neprime

Exemplu:
Intrare

5
9 7 1 2 3
Ieșire

2 1 3 9 7 
2 1 7 9 3 
2 9 3 1 7 
2 9 7 1 3 
3 1 2 9 7 
3 1 7 9 2 
3 9 2 1 7 
3 9 7 1 2 
7 1 2 9 3 
7 1 3 9 2 
7 9 2 1 3 
7 9 3 1 2 
Explicație
În permutările generate valorile prime (2 3 7) nu apar pe poziții alăturate.

## Cod sursă C++

```cpp
#include <iostream>
using namespace std;
int n , x[20], A[20] , uz[20], pp[20];
bool Prim(int n)
{
	if(n < 2)
		return false;
	if(n == 2)
		return true;
	if(n % 2 == 0)
		return false;
	for(int d = 3 ; d * d <= n ; d ++)
		if(n % d == 0)
			return false;
	return true;
}
void Afisare(int L)
{
    for(int i = 1 ; i <= L ; i ++)
        cout << A[x[i]] << " ";
    cout << '\n';
}
bool ok(int k)
{
	if(k == 1)
		return true;
    if(uz[ x[k] ] == 1)
        return false;
    if(pp[x[k]])
        if(pp[x[k-1]])
            return false;
    return true;
}
void Back(int k)
{
    for(int i = 1 ; i <= n ; i ++)
    {
        x[k] = i;
        if(ok(k))
        {
            uz[i] = 1;
            if(k == n)
                Afisare(n);
            else
                Back(k+1);
            uz[i] = 0;
        }
    }
}
int main()
{
    cin >> n;
    for(int i = 1 ; i <= n ; i ++)
		cin >> A[i], pp[i] = Prim(A[i]);
	for(int i = 1 ; i < n ; i ++)
		for(int j = i + 1 ; j <= n ; j ++)
			if(A[i] > A[j])
				swap(A[i] , A[j]), swap(pp[i] , pp[j]);
    Back(1);
    return 0;
}
```

## Resurse

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