# PBinfo #3605 – descprime – Rezolvare C++

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

## Enunț

Cerința
Se dă un număr natural nenul S. Să se determine numărul de moduri de a-l scrie pe S ca sumă de numere prime distincte, precum și o modalitate de a-l scrie pe S ca sumă de cât mai multe numere prime distincte.

Date de intrare
Programul citește de la tastatură numărul S.

Date de ieșire
Programul va afișa la ecran pe prima linie numărul nrSol, reprezentând numărul de moduri de a-l scrie pe S ca sumă de numere prime distincte, iar pe a doua linie o modalitate de a-l scrie pe S ca sumă de cât mai multe numere prime distincte. Dacă sunt mai multe soluții, se va afișa cea minimă lexicografic, iar numerele prime din soluție se vor scrie în ordine crescătoare.

Restricții și precizări

1 ≤ S ≤ 100

Exemplu:
Intrare

20
Ieșire

4
2 5 13
Explicație
Sunt patru soluții: 3 17, 2 5 13, 7 13, 2 7 11. Dintre acestea, soluția care are cele mai multe numere prime și este minimă lexicografic este 2 5 13.

## Cod sursă C++

```cpp
#include <iostream>
using namespace std;
int prime[40], n, a[40], S;
int t[101]; /// pentru ciur
int sume[40]; /// sume partiale in stiva
int sol[40], k; /// retinem solutia cu numar maxim de numere prime
int nrSolutii;
void Ciur(int M)
{
    int i, j;
    for (i = 3; i * i <= M; i += 2)
        if (t[i] == 0)
            for (j = i * i; j <= M; j = j + 2 * i)
                t[j] = 1;
    n = 1;
    prime[1] = 2;
    for (i = 3; i <= M; i += 2)
        if (t[i] == 0) prime[++n] = i;
}
void Solutie(int top)
{
    nrSolutii++;
    if (top > k)
    {
        k = top;
        for (int i = 1; i <= top; i++)
            sol[i] = prime[a[i]];
    }
}
int Valid(int top)
{
    sume[top] = sume[top - 1] + prime[a[top]];
    if (sume[top] > S) return 0;
    return 1;
}
void Back()
{
    int cand, top;
    top = 1;
    a[top] = 0;
    while (top > 0)
    {
        cand = 0;
        while (!cand && a[top] < n)
        {
            a[top]++;
            cand = Valid(top);
        }
        if (!cand) top--;
        else if (sume[top] == S) Solutie(top);
        else
        {
            top++;
            a[top] = a[top - 1];
        }
    }
}
void Afisare()
{
    cout << nrSolutii << "\n";
    for (int i = 1; i <= k; i++)
        cout << sol[i] << " ";
    cout << "\n";
}
int main()
{
    Ciur(100);
    cin >> S;
    Back();
    Afisare();
    return 0;
}
```

## Resurse

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